Array Matrix Breadth First Search
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) = 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 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 * largestSide
Run your code to see the result.