CODEWITHSUNDEEP
algorithmmatrix
Zachary Carter
Zachary Carter

Reputation: 373

All rectangles in grid with common corner

I'd like to take a grid of 0's and 1's and arrive at all rectangles present in the grid, which share a common corner.

Similar to the Maximal Rectangle problem - Link 1 Link 2

But instead of finding a single rectangle with the maximum area, I'd like to find all rectangles that share a common corner. IE if I specify coordinates (10,10) I'd like all possible rectangles that have a bottom left corner of 10,10.

Could someone help explain how I can adapt the implementation of the algorithm I linked to do what I described?

Upvotes: 0

Views: 724

Answers (2)

j_random_hacker
j_random_hacker

Reputation: 51326

You don't want or need my linked answer for this. An easy way to do this is to first calculate the "integral image" I[][] of the input matrix M[][] -- that is, a matrix I[][] whose (x, y) entry is the sum of all entries below and to the left of (x, y) in the input matrix. This lets you easily compute the number of 1s in any given rectangle (x1, y1, x2, y2) in constant time using I[x2][y2] - I[x1-1][y2] - I[x2][y1-1] + I[x1-1][y1-1], if (x1, y1) is the bottom-left corner and (x2, y2) is the top-right corner. I[][] can be computed in a one-time O(n^2) preprocessing step.

For a given bottom-left corner (x1, y1), you can then simply loop through all widths w and heights h in increasing order using a pair of nested loops, testing whether the number of 1s in the rectangle (x1, y1, x1+w, y2+h) is the number of 1s that should be there in an all-1 rectangle -- i.e., (b+1)*(h+1). As soon as this fails to hold, exit that loop early (since clearly if some rectangle is not an all-1 rectangle, then no rectangle that contains it can be either).

This algorithm is of course O(n^2)-time for an n*n rectangle, but there is no avoiding this worst case (consider an input matrix in which every entry is 1).

Upvotes: 1

div
div

Reputation: 573

I am not sure about how to adapt the given algorithm for this problem, but I have a good way to solve this problem.

Say, we are given the bottom-left corner for the rectangles at (x1, y1). We keep a count of the number of rectangles(with value 1 and sharing the bottom-left corner) num and a horizontal value till which rectangles can be found at this value of y hval. Now, we traverse horizontally until hval or if we find a 0 in the way, since no rectangles can be made beyond this point. Now, we make this x the new hval. We move to the next row and do the same each time counting the number of rectangles we have passed.

The solution is O(n2). Since we used atmost 2*num steps the complexity of solution is also bounded by θ(num).

This python code sample can provide a better understanding:

num = 0
hval = len(board)
i = 1
x1=1
y1=1
x2 = x1
while (y1 < len(board) and i > 0):
    i = 0
    while (board[y1][x2] == 1 and x2 < hval):
        num += 1
        x2 += 1
        i += 1
    else:
        hval = x2
        y1 += 1
        x2 = x1
print(num)

Upvotes: 1

Related Questions