Array Dynamic Programming Matrix Tabulation
Proficient Level

Implement the maximumSquareOfOnes method that returns the area of the largest square containing only 1 values.

The input contains a binary matrix grid with rows rows and cols columns. Each cell contains either 0 or 1.

Your task is to find the largest square that contains only 1 values and return its area. For example, if the largest valid square has side length 2, the returned area should be 4.

Example 1
Input:
grid (int[][]) = [[1,0,1,0],[1,0,1,1],[1,1,1,1]]
rows (int) = 3
cols (int) = 4
Return:
(int) 4
Example 2
Input:
grid (int[][]) = [[0,1],[1,0]]
rows (int) = 2
cols (int) = 2
Return:
(int) 1
Example 3
Input:
grid (int[][]) = [[0]]
rows (int) = 1
cols (int) = 1
Return:
(int) 0

This problem can be solved by checking how large a square can end at each cell.

If a cell contains 0, no square of ones can end there. If it contains 1, its square size depends on the top, left, and top-left neighboring cells. The current cell can extend the smallest of those three square sizes by one.

Keep track of the maximum side length found while filling the table. The final answer is the square of that side length because the problem asks for area.

Pseudocode:

function maximumSquareOfOnes(grid, rows, cols):
    if rows == 0 or cols == 0:
        return 0
    dp = 2D array of rows x cols filled with 0
    maxSide = 0
    for i from 0 to rows - 1:
        for j from 0 to cols - 1:
            if grid[i][j] == 1:
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
                maxSide = max(maxSide, dp[i][j])
    return maxSide * maxSide
Run your code to see the result.