Count the number of trues in a 2D subarray

Question

Given a 2D array of Boolean:

{{false, false, true, false, true}
{true, false, true, false, false}
{false, true, false, false, false}
{false, false, false, false, false}
{true, true, true, true, true}}

And you can't directly access the array, it must be through a ready-made method hasTrue that takes in the start point and endpoint of subarray of the above 2D array and return a boolean if this subarray has at least 1 true.

boolean hasTrue(int startX, int startY, int endX, int endY)

For Example, if we want to check the area from index (0,0) to (1,1) we will call hasTrue(0,0,1,1) and it will return true since index (1,0) has the value true. and we can give it the same endpoint as the start. for Example, hasOnes(0,0,0,0) this will check only a single index of the array which holds value false and will return false.

I need to implement a method that counts the number of the trues in a given subarray and I must use hasTrue method.

int countTrues(int startX, int startY, int endX, int endY)

One Solution is to brute force from the start index to the end and count the number of indices that have true. But in the best case complexity it will be n*m.

Another solution I am thinking of is to implement a recursive method that passes the whole subarray at once to hasOnes() and if the whole subarray returns false then I would not need to go through all the indices I will just return 0 which will be the best case O(1).

If it returns true I will split the array and check every half, and continue to do so and count the number of trues.

How can I implement the second solution?

Answer 1

I'll write C++ code (sorry) as forgot Java, but still can help you. Sure it won't be difficult to convert to Java. It implements your idea of recursively dividing into halfs, actually it divides into 4 almost-equal quadrants (sub-rectangles).

int countTrues(int xb, int yb, int xe, int ye) { // x/y begins/ends
    if (xb > xe || yb > ye) // zero-size (empty) array
        return 0;
    bool h = hasTrue(xb, yb, xe, ye);
    if (!h || (xb == xe && yb == ye)) // all-false or single-element array
        return (h ? 1 : 0);
    int xm = (xb + xe) / 2, ym = (yb + ye) / 2; // middle (center) point
    return ( // sum counts of 4 almost-equal quadrants (sub-rectangles)
        countTrues(xb, yb, xm, ym) +       // top-left
        countTrues(xm + 1, yb, xe, ym) +   // top-right
        countTrues(xb, ym + 1, xm, ye) +   // bottom-left
        countTrues(xm + 1, ym + 1, xe, ye) // bottom-right
    );
}