Naive way to find largest block in a rectangle of 1's and 0's

Question

I'm trying to come up with the bruteforce(naive) solution to find the largest block of 1 or 0 in a rectangle of 1 and 0. I know optimal ways which can do it in O(n) time where n is the total size of rectangle.

1 1 0 1 0 1
1 0 0 0 1 1
1 0 0 0 1 1
1 1 0 1 1 0

In the above rectangle, it is rectangle starting at (Row 2, Col 2) of size 6. I was thinking this..

Go through each element and then find the size it makes by iterating in all directions from it.

Is it bruteforce? What will be the complexity? I'm going through all elements that is n, but then I'm iterating in all directions, how much will that be?

I'm aware that this question has been asked 100 times, but they talk about optimal solutions. What I'm looking for is a bruteforce solution and its complexity?

Answer 1

The algorithm you described looks somehow like this C code:

//for each entry
for(int x = 0; x < width; ++x)
    for(int y = 0; y < height; ++y)
    {
        char lookFor = entries[x][y];
        int area = 0;
        for(int row = y; row < height; ++row)
        {
            if(entries[x, row] != lookFor)
                break;
            for(int col = x; col < width; ++col)
            {
                if(entries[col, row] != lookFor)
                    break;
                int currentArea = (col - x + 1) * (row - y + 1);
                if(currentArea > area)
                {
                    //save the current rect
                }
            }
        }
    }

There are four nested loops. The outer loops will iterate exactly n times (with n being the number of entries). The inner loops will iterate width * f1 and height * f2 times in average (with f1 and f2 being some constant fraction). The rest of the algorithm takes constant time and does not depend on the problem size.

Therefore, the complexity is O(n * f1 * width * f2 * height) = O(n^2), which essentially means "go to each entry and from there, visit each entry again", regardless of whether all entries really need to be checked or just a constant fraction that increases with the problem size.

Edit

The above explanations assume that the entries are not distributed randomly and that for larger fields it is more likely to find larger homogeneous subregions. If this is not the case and the average iteration count for the inner loops does not depend on the field size at all (e.g. for randomly distributed entries), then the resulting time complexity is O(n)

Answer 2

Brute force is generally split into two (sometimes sequential) parts. The first part is generating all possible candidates for solutions to the problem. The second part is testing them to see if they actually are solutions.

Brute force: Assume your rectangle is m x n. Generate all sub-rectangles of size a x b where a is in {1..m} and b is in {1..n}. Set a maximum variable to 0. Test all sub-rectangles to see if it is all 0s and 1s. If it is, let maximum = max(maximum, size(sub-rectangle). Alternatively simply start by testing the larger sub-rectangles and move towards testing smaller sub-rectangles. As soon as you find a sub-rectangle with all 0s or 1s, stop. The time complexity will be the same because in the worst-case for both methods, you will still have to iterate through all sub-rectangles.

Time complexity:

Let's count the number of sub-rectangles generated at each step.

There are m*n subrectangles of size 1 x 1.

There are (m-1)*n subrectangles of size 2 x 1.

There are m*(n-1) subrectangles of size 1 x 2.

There are (m-1)*(n-1) subrectangles of size 2 x 2.

... < and so forth >

There are (m-(m-1))*(n-(n-1)) subrectangles of size m x n.

Thus the formula for counting the number of subrectangles of size a x b from a larger rectangle of size m x n is simply:

number_of_subrectangles_of_size_a_b = (m-a) * (m-b)

If we imagine these numbers laid out in an arithmetic series we get

1*1 + 1*2 + ... + 1*n + 2*1 + ... + m*n

This can be factored to:

(1 + 2 + ... + m) * (1 + 2 + ... + n).

These two arithmetic series converge to the order of O(m²) and O(n²) respectively. Thus generating all sub-rectangles of an m*n rectangle is O(m²n²). Now we look at the testing phase.

After generating all sub-rectangles, testing if each sub-rectangle of size a x b is all 0s or all 1s is O(a * b). Unlike the previous step of generating sub-rectangles of size a x b which scales upwards as a x b decreases, this step increases proportionally with the size of a x b.

e.g.: There is 1 sub-rectangle of size m x n. But testing to see if that rectangle is all 0s or all 1s takes O(m*n) time. Conversely there are m*n sub-rectangles of size 1. But testing to see if those rectangles are all 0s or all 1s takes only O(1) time per rectangle.

What you finally end up for the time complexity is a series like this:

O( (m-(m-1))(n-(n-1))*(mn) + (m-(m-1))(n-(n-2))*m(n-1)... + mn*(m-(m-1))(n-(n-1)) )

Note 2 things here.

1. The largest term in the series is going to be somewhere close to (m / 2)(n / 2)(m / 2) (n / 2) which is O(m²n²)

2. There are m * n terms total in the series.

Thus the testing phase of the brute-force solution will be O(mn * m²n²) = O(m³n³).

Total time complexity is:

O(generating) + O(testing) = O(m2n2 + m3n3) = O(m3n3)

If the area of the given rectangle is say, N, we will have O(N³) time complexity.