Leetcode — 221. Maximal Square

The link to the problem: https://leetcode.com/problems/maximal-square/

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

For example, 
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4 (shown in below graph)

example graph (Photo Credit to Leetcode)

Thoughts:

At first, I thought the way how we can solve this problem will be similar to the way how we solve Number of Islands. In Number of Islands, we can use DFS to keep merging all the adjacent cells that contain 1. However, in this problem, we have the condition to find a SQUARE only. We cannot consider any other graphs like a rectangle or an “island-like” graph. i.e., DFS doesn’t seem to be the easiest way to solve this problem.

🔲If we only need to search for a one-length square, that will be a lot easier. We just need to find a cell that contains one. What if we need to find a square with a length that is two, or more?

Assume we traverse the given matrix from top left (i.e., from (0,0) to the right till the end of the row, then going down to the next row…).
Hence, the first cell we reach “the potential square” will be the top-left cell of the square. How do we know the max length of the square this cell can involve in?

It won’t be too hard if we want to find a two-length square from the current position (i, j). We only need to find if its right cell (i, j+1), its bottom cell (i+1, j), and its bottom-right cell (i+1, j+1) all contain 1s.

If we want to find a three-length square, not only we need to check those three cells but also the right cell of its right cell, the bottom cell of its bottom cell, the bottom-right cell of its bottom-right cell, … we need to check 7 cells to see whether they all contain 1s. There is no need to say if we find four, or five,… it will be time-consuming if we just try to find the length one by one.

However, if we draw an n*n square, we can actually find that an n*n square can include FOUR overlapped (n-1)*(n-1) squares. Shown in the below graph.

a 3x3 square contains four overlapped 2x2 squares

When we write down the max length of the square on the top-left cell of each square, will be like in the below graph. We can see that 3 is surrounded by three 2s, and this is actually the same thing

當我們把各個正方形的左上角的格子寫下這個正方形的最長長度時, 就會如下圖所示, 我們可以清楚的看到3被3個2包圍, 這也是因為我們上述提到的特性, 當我們可以組成4個(包含自己) 2*2的正方形時, 代表這裡可以組成一個3*3的正方形,
因此想知道某位置(i,j) 最長可以組成多少長度的正方形, 我們只要注意其右方格, 右下格, 及下方格 的數字即可, 而我們程式碼將利用這個特性來幫忙找最長長度的正方形

Only write the length in the top-left corner of the square.

Code Logic:

Since we need to find the max length square of this cell depend on its three adjacent cells (right, bottom, bottom-right), it is important to use a 2D array to store the max length for every cell. (And yes, this is what dynamic programming doing!)

The code logic will be we always refer to the length of its right cell, bottom cell, and right-bottom cell. After we find those lengths, we will consider this cell can form a square with the length of “minimum length among those” + 1. There will be several examples below to explain in detail.

⚠️Two important bullet points:

1. We will traverse the given matrix from the bottom right corner (m-1,n-1) and back to the top left corner (0,0). The reason is that since we need to reference the current cell’s right, bottom, and bottom-right, it is necessary that we first traverse those cells before the current cell!
2. When the cell is on the right-most column, or on the most bottom row of the matrix, we can at most form a length of one square since there’s no space on its right or its bottom.

👷Why can we consider the maximum length of the current cell is the minimum length among adjacent cells plus one ❓

Actually, we can also say, we choose the maximum length that all three adjacent cells are guaranteed to form; plus one is just because we can include the current cell to help form/expand a square. We can see below three different situations to understand why. Assume our current position is at (0,0) in all situations.

🚧1. If the given matrix looks like this …

matrix example(1)

We refer to the length in three adjacent cells:
right (0, 1) — 3 ; bottom (1, 0) — 0; bottom (1, 0) — 2

Hence, we select the minimum one and plus 1. Starts from (0, 0), the maximum length of the square we can form is 1.

🚧2. If the given matrix looks like this …

matrix example(2)

We refer to the length in three adjacent cells:
right (0, 1) — 2; bottom (1, 0) — 2; bottom (1, 0) — 1

Hence, we select the minimum one and plus 1. Starts from (0, 0), the maximum length of the square we can form is 2.

🔧From here, we can see why it is guaranteed to have a two-length square from (0, 0). Since both the right cell and the bottom cell are guaranteed to form a 2-length square from the cell, it means they guarantee their adjacent cells within the distance 2 are all 1s.

🚧3. If the given matrix looks like this …

matrix example(3)

We refer to the length in three adjacent cells:
right (0, 1) — 3; bottom (1, 0) — 2; bottom (1, 0) — 2

Hence, we select the minimum one and plus 1. Starts from (0, 0), the maximum length of the square we can form is 3.

🔧Just like the above situation, this time all three adjacent cells can guarantee the cells that are in the distances of 2 from each cell are all 1s. That is to say, we can expand the 2*2 square into 3*3 square if we include (0,0).

Below is the 4ms code that beats 87% —

public int maximalSquare(char[][] matrix) {
        int max = 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        for(int i=m-1;i>=0;i--)
        {
            for(int j=n-1;j>=0;j--)
            {
                if(matrix[i][j]=='0')
                    continue;
                if(i==m-1||j==n-1)
                    dp[i][j] = 1;
                else
                {
                    dp[i][j] = Math.min(dp[i+1][j],dp[i][j+1]);
                    dp[i][j] = 1+Math.min(dp[i+1][j+1],dp[i][j]);
                }
                if(dp[i][j] > max)
                    max = dp[i][j];
            }
        }
        return max*max;
    }

⚠️If you are only used to traverse an array from the top left, you can also change to record the max length of the square at the bottom-right corner, instead of the top-left corner. Hence, you should always check the current cell’s left cell, top cell, and its top-left cell:

public int maximalSquare(char[][] matrix) {
        int max = 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(matrix[i][j]=='0')
                    continue;
                if(i==0||j==0)
                    dp[i][j] = 1;
                else
                {
                    dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j]);
                    dp[i][j] = 1+Math.min(dp[i][j],dp[i-1][j-1]);
                }
                if(dp[i][j]>max)
                    max = dp[i][j];
            }
        }
        return max*max;
    }