Intermediate Level
Implement the maximalSquareMatrixArea method that returns the area of the largest square containing only 1 values.
The input matrix grid contains only 0 and 1 values, along with its rows and cols.
Your task is to find the largest square submatrix that contains only 1s and return its area. The area is calculated as side × side.
For example, in [[1,0,1],[1,1,1],[1,1,1]], the largest square of 1s has side length 2, so the answer is 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 remember the largest square that can end at each cell.
If a cell contains 0, no square of 1s can end there. If a cell contains 1, check its top, left, and top-left diagonal cells. The current square side becomes 1 + minimum(top, left, diagonal).
Track the largest side length found while scanning the matrix. At the end, return largestSide * largestSide.
Pseudocode:
function maximalSquareMatrixArea(grid, rows, cols):
create dp matrix filled with 0
largestSide = 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])
if dp[i][j] > largestSide:
largestSide = dp[i][j]
return largestSide * largestSideReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run