Array String Dynamic Programming Memoization Tabulation
Proficient Level

Implement the maximumSquareAreaOnes method that returns the area of the largest all-ones square in a matrix.

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 area that contains only 1 values. The method should return the area of the square, not the side length.

For example, if the largest all-ones square has side length 2, the returned area should be 4.

Example 1
Input:
grid (int[][]) = [[1,0,1],[1,1,1],[1,1,1]]
rows (int) = 3
cols (int) = 3
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,0],[0,0]]
rows (int) = 2
cols (int) = 2
Return:
(int) 0

Use dynamic programming to calculate the largest square that can end at each cell.

If a cell contains 0, no all-ones square can end there. If a cell contains 1, its square side depends on the top, left, and top-left neighboring cells.

The side length at the current cell is 1 + minimum(top, left, top-left). Track the largest side length found and return its square as the final area.

Pseudocode:

function maximumSquareAreaOnes(grid, rows, cols):
    create dp matrix with zero values
    maxSide = 0
    for r from 0 to rows - 1:
        for c from 0 to cols - 1:
            if grid[r][c] == 1:
                if r == 0 or c == 0:
                    dp[r][c] = 1
                else:
                    dp[r][c] = 1 + minimum(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1])
                maxSide = maximum(maxSide, dp[r][c])
    return maxSide * maxSide
Run your code to see the result.