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) =
3cols (int) =
3Returns (int)
4Example 2
Input
grid (int[][]) =
[[0,1],[1,0]]rows (int) =
2cols (int) =
2Returns (int)
1Example 3
Input
grid (int[][]) =
[[0,0],[0,0]]rows (int) =
2cols (int) =
2Returns (int)
0Use 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 * maxSideReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run