[ACCEPTED]-Dynamic programming - Largest square block-dynamic-programming

Here is a sketch of the solution:

For each 13 of the cells we will keep a counter of how 12 big a square can be made using that cell 11 as top left. Clearly all cells with 0 will 10 have 0 as the count.

Start iterating from 9 bottom right cell and go to bottom left, then 8 go to one row up and repeat.

At each scan 7 do this:

1. If the cell has 0 assign count=0
2. If the cell has 1 and is an edge cell (bottom or right edge only), assign count=1
3. For all other cells, check the count of the cell on its right, right-below, and below. Take the min of them and add 1 and assign that to the count. Keep a global max_count variable to keep track of the max count so far.

At the end of traversing the matrix, max_count will 6 have the desired value.

Complexity is no 5 more that the cost of traversal of the matrix.

This 4 is how the matrix will look like after the 3 traversal. Values in parentheses are the 2 counts, i.e. biggest square that can be 1 made using the cell as top left.

1(1) 0(0) 1(1) 0(0) 1(1) 0(0)
1(1) 0(0) 1(4) 1(3) 1(2) 1(1)
0(0) 1(1) 1(3) 1(3) 1(2) 1(1)
0(0) 0(0) 1(2) 1(2) 1(2) 1(1)
1(1) 1(1) 1(1) 1(1) 1(1) 1(1)

Implementation in Python

def max_size(mat, ZERO=0):
    """Find the largest square of ZERO's in the matrix `mat`."""
    nrows, ncols = len(mat), (len(mat[0]) if mat else 0)
    if not (nrows and ncols): return 0 # empty matrix or rows
    counts = [[0]*ncols for _ in xrange(nrows)]
    for i in reversed(xrange(nrows)):     # for each row
        assert len(mat[i]) == ncols # matrix must be rectangular
        for j in reversed(xrange(ncols)): # for each element in the row
            if mat[i][j] != ZERO:
                counts[i][j] = (1 + min(
                    counts[i][j+1],  # east
                    counts[i+1][j],  # south
                    counts[i+1][j+1] # south-east
                    )) if i < (nrows - 1) and j < (ncols - 1) else 1 # edges
    return max(c for rows in counts for c in rows)

LSBRA(X,Y) means "Largest Square with Bottom-Right 20 At X,Y"

Pseudocode:

LSBRA(X,Y):
   if (x,y) == 0:
       0
   else:
       1+MIN( LSBRA(X-1,Y), LSBRA(X,Y-1), LSBRA(X-1,Y-1) )

(For edge cells, you can 19 skip the MIN part and just return 1 if (x,y) is 18 not 0.)

Work diagonally through the grid 17 in "waves", like the following:

    0 1 2 3 4
  +----------
0 | 1 2 3 4 5
1 | 2 3 4 5 6
2 | 3 4 5 6 7
3 | 4 5 6 7 8

or alternatively, work 16 through left-to-right, top-to-bottom, as 15 long as you fill in edge cells.

    0 1 2 3 4
  +----------
0 | 1 2 3 4 5
1 | 6 7 8 9 .
2 | . . . . .
3 | . . . . .

That way 14 you'll never run into a computation where 13 you haven't previously computed the necessary 12 data - so all of the LSBRA() "calls" are actually 11 just table lookups of your previous computation 10 results (hence the dynamic programming aspect).

Why it works

In 9 order to have a square with a bottom-right 8 at X,Y - it must contain the overlapping 7 squares of one less dimension that touch 6 each of the other 3 corners. In other words, to 5 have

XXXX
XXXX
XXXX
XXXX

you must also have...

XXX.    .XXX    ....    ....
XXX.    .XXX    XXX.    ....
XXX.    .XXX    XXX.    ....
....    ....    XXX.    ...X

As long as you 4 have those 3 (each of the LSBRA checks) N-size 3 squares plus the current square is also 2 "occupied", you will have an (N+1)-size 1 square.

The first algorithm that comes to my mind 6 is:

1. '&&' column/row 1 with column/row 2 if, this is to say do an '&&' operation between each entry and its corresponding entry in the other column/row.
2. Check the resulting column, if there are any length 2 1's that means we hit a 2x2 square.
3. And the next column with the result of the first two. If there are any length 3 1's we have hit a 3x3 square.
4. Repeat until all columns have been used.
5. Repeat 1-4 starting at column 2.

I won't show you the implementation as 5 its quite straightforward and your problem 4 sounds like homework. Additionally there 3 are likely much more efficient ways to do 2 this, as this will become slow if the input 1 was very large.

Let input matrix is M: n x m

T[i][j] is DP matrix 8 which contains largest square side with 7 squares bottom right angle (i,j).

General rule 6 to fill the table:

if (M[i][j] == 1) {
  int v = min(T[i][j-1], T[i-1][j]);
  v = min(v, T[i-1][j-1]);
  T[i][j] = v + 1;
}
else 
  T[i][j] = 0;

The result square size 5 is max value in T.

Filling T[i][0] and T[0][j] is trivial.

I 4 am not sure if this algo can be used for 3 your huge file, but you don't need to store entire matrix T but only current and previous 2 lines only.

Following notes can help to undestand 1 general idea:

• all squares with right bottom angles (i-1, j), (i, j-1), (i-1, j-1) with size s are inside square of with right bottom angle (i, j) with size s+1.
• if there is square of size s+1 with right bottom corner at (i, j), then size of maximal square with right bottom angles (i-1, j), (i, j-1), (i-1, j-1) is at least s.
• Opposite is also true. If size of at least one square with bottom right angles at (i-1, j), (i, j-1), (i-1, j-1) is less then s, then size of square with right bottom corner at (i, j) can not be larger then s+1.

OK, the most inefficient way but simple 18 would be:

1. select first item. check if 1, if 17 so you have a 1x1 square.

2. check one below 16 and one to right, if 1, then check row 2 15 col 2, if 1, 2x2 square.

3. check row 3 col 14 1, col 2 and col 3, plus row 1 col 3, row 13 2 col 3, if 1, 3x3.

4. So basically you keep 12 expanding the row and col together and check 11 all the cells inside their boundaries. As 10 soon as you hit a 0, it's broken, so you 9 move along 1 point in a row, and start again.

5. At 8 end of row, move to next row.

6. until the end.

You 7 can probably see how those fit into while 6 loops etc, and how &&s can be used to check 5 for the 0s, and as you look at it, you'll 4 perhaps also notice how it can be sped up. But 3 as the other answer just mentioned, it does 2 sound a little like homework so we'll leave 1 the actual code up to you.

Good luck!

The key here is that you can keep track 17 of the root of the area instead of the actual 16 area, using dynamic programming.

The algorithm 15 is as follow:

Store an 2D array of ints 14 called max-square, where an element at index 13 i,j represents the size of the square it's 12 in with i,j being the bottom right corner. (if 11 max[i,j] = 2, it means that index i,j is 10 the bottom right corner of a square of size 9 2^2 = 4)

For each index i,j:

if at i,j the element 8 is 0, then set max-square i,j to 0.

else:

Find 7 the minimum of max-square[i - 1, j] and max-square[i, j 6 - 1] and max-square[i - 1][j -1]. set max-square[i, j] to 5 1 + the minimum of the 3. Inductively, you'll 4 end up filling in the max-square array. Find/or 3 keep track of the maximum value in the process, return 2 that value^2.

Take a look at these solutions 1 people have proposed: https://leetcode.com/discuss/questions/oj/maximal-square?sort=votes

Let N be the amount of cells in the 2D array. There 19 exists a very efficient algorithm to list 18 all the maximum empty rectangles. The largest 17 empty square is inside one of these empty 16 rectangles, and founding it is trivial once 15 the list of the maximum empty rectangles 14 has been computed. A paper presenting a 13 O(N) algorithm to create such a list can 12 be found at www.ulg.ac.be/telecom/rectangles as well as source code (not 11 optimized). Note that a proof exists (see 10 the paper) that the number of largest empty 9 rectangles is bounded by N. Therefore, selecting 8 the largest empty square can be done in 7 O(N), and the overall method is also O(N). In 6 practice, this method is very fast. The 5 implementation is very easy to do, since 4 the whole code should not be more than 40 3 lines of C (the algorithm to list all the 2 maximum empty rectangles takes about 30 1 lines of C).