leetcode Question: Maximal Square

Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

For example, given the following matrix:

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

Return 4.

Analysis:

This is an DP problem. Usually in DP, all we need is to find out or define the transition function. Implementation part is then straightforward. For a DP problem, define the transition function is to find "how the solution of current state can be derived from only the previous state but not other states".   Now, let's see this problem.

The problem requires the square contains all 1's to be largest. Any square in this matrix is defined with three parameters:  x (row), y (column) and w (width).  To find the largest matrix, at least we will search every (x, y), to see if the square starts/ends in (x, y) are the target we need. One of the key point in this problem is the starts/ends. Let's see the figure below:

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

For the colored square, we may say

1. This square starts from (0, 0) (top-left) with width 2, 

2. This square ends at (1, 1) with width 2.

In DP, we need to keep the result in every state, an matrix state[][] is needed.

We initialize the state[][] :   for each position (x, y) in state, if matrix[x][y] == '1', state[x][y] = 1

Because 1*1 the element itself is also a square if its value is '1'. state[x][y] is recording the largest square width that ends at (x, y).  Why using ends? Because we have to utilize the previous states (here you can imagine the states is the largest width that were computed in previous positions.). If we use the position as the starting point, it's hard to get the previous states because we will checking the 'future' states which are not available. See the figure below, we are search from top-left to bottom-right,  

For position (3,3) which is marked red 1, we can derive the largest square that ends at this point by checking its previous positions. The square with width 3 that ends at (3, 3) is a combination of four squares:
1. Square that ends at (2,2) with width 2  (green square)
2. Square that ends at (3,2) with width 2  (orange square)
3. Square that ends at (2,3) with width 2  (blue square)
4. (3, 3) itself. (red 1)

If all the squares are all 1's, state[3][3] is then become 2+1 = 3. However in the above figure, condition 1 is an all 1's square, condition 2  and 3 are not. So the largest square the ends at (3, 3) cannot be 2 + 1 = 3.  Also it cannot be 1+1 = 2 because condition 1,2,3 with with 1 are not true (see green 1, blue 1, orange 0 and red 1 in the figure).  In short, we derive the transition function:

state[x][y] = 1 + min{state[x-1][y], state[x][y-1], state[x-1][y-1]}

Given this function, the implementation is now pretty straightforward.

Code(C++):

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int row = matrix.size();
        if (row == 0) {return 0;}
        int col = matrix[0].size();
        
        vector<vector<int> > state (row, vector<int>(col));
        
        int res = 0;
        for (int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if (matrix[i][j] == '1'){
                    state[i][j] = 1;
                    res = 1;
                }
            }
        }

        for (int i=1;i<row;i++){
            for(int j=1;j<col;j++){
                if (state[i][j] != 0){
                    state[i][j] = 1 + min(state[i-1][j], min(state[i][j-1],state[i-1][j-1]));
                    if (res<state[i][j]){ res = state[i][j]; }
                }
            }
        }
        return res*res;
    }
};

Code(Python):

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        res = 0
        row = len(matrix)
        if row == 0:
            return res
        col = len(matrix[0])
        state = [[0 for y in range(col)] for z in range(row)]
        
        for i in range(row):
            for j in range(col):
                if matrix[i][j] == '1':
                    state[i][j] = 1
                    res = 1
                    
        for i in range(1, row):
            for j in range(1,col):
                if state[i][j] != 0:
                    state[i][j] = 1+ min(min(state[i-1][j],state[i-1][j-1]),state[i][j-1])
                    if res < state[i][j]:
                        res = state[i][j]
        return res*res