LeetCode221

221. Maximal Square

Reference: https://discuss.leetcode.com/topic/20801/extremely-simple-java-solution

Thanks jaqenhgar ! Really F**king Genius.

1. Description:

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 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.

2. Difficulty:

Medium

3. Relative Problems:

84. Largest Rectangle in Histogram
85. Maximal Rectangle

4. Solution:

Input 2D matrix. Return int maxArea.

Main Idea: Dynamic Programming.

Cause it is a Dynamic Programming question, we should find the state equation.

So I create a 2D matrix edge to store the length of edge of square.(As the point is in the bottom right)

For an element which = 1, I consider it as a square which edge = 1.

To find a square, we need to check ( i, j - 1 ) , (i - 1, j) , (i - 1, j - 1).

If it is all 1, ? = 2.

1 1
1 ?

If it is one element = 0 , ? = 1, we can not get a bigger square!

1 0
1 ?

If it is all 2, ? = 3.

1 1 1
1 2 2
1 2 ?

You could try this matrix to see whether you can get correct edge, and it would be much more clear for us to understand !

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

For such matrix, we could get edge

0 0 0 0 0 0
0 1 0 1 0 0
0 1 0 1 1 1
0 1 1 1 2 1
0 1 0 0 1 0

6. Code

if(matrix.length == 0)
    return 0;
  int[][] edge = new int[matrix[0].length + 1][matrix.length + 1];//save length of edge
  int maxArea = 0;
  for(int i = 1; i < edge.length; i++){
      for (int j = 1; j < edge.length; j++){
          if(matrix[i - 1][j - 1] == '1'){
              edge[i][j] = Math.min(Math.min(edge[i][j - 1],edge[i - 1][j]),edge[i - 1][j - 1])+1;
              //if matrix[i - 1][j - 1] == 1,length at least = 1.
              //if left,top,top left is all 1. Then it must be a square which edge = 2!
              //if left,top,top left square edge is 2. Then it must be a square which edge = 3!
              maxArea = (int) Math.max(maxArea,Math.pow(edge[i][j],2));
          }
      }
  }
  return maxArea;