Maximal Square

medium dp grid

Problem

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Inputgrid = [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]

Output4

dp[i][j] = side length of the largest all-ones square ending at (i, j). When grid[i][j] = 1, dp[i][j] = 1 + min(dp[i−1][j], dp[i][j−1], dp[i−1][j−1]).

grid (rows separated by ;)

def maximal_square(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    best = 0
    for i in range(m):
        for j in range(n):
            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])
                best = max(best, dp[i][j])
    return best * best

function maximalSquare(grid) {
  const m = grid.length, n = grid[0].length;
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));
  let best = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j]) {
        dp[i][j] = (i === 0 || j === 0) ? 1 : 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
        best = Math.max(best, dp[i][j]);
      }
    }
  }
  return best * best;
}

class Solution {
    public int maximalSquare(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        int best = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    dp[i][j] = (i == 0 || j == 0) ? 1
                        : 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
                    best = Math.max(best, dp[i][j]);
                }
            }
        }
        return best * best;
    }
}

int maximalSquare(vector<vector<char>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    int best = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                dp[i][j] = (i == 0 || j == 0) ? 1
                    : 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
                best = max(best, dp[i][j]);
            }
        }
    }
    return best * best;
}

Explanation

We want the biggest solid square of 1s. The key trick is to let dp[i][j] mean the side length of the largest all-ones square whose bottom-right corner sits exactly at cell (i, j).

For a cell to be the corner of, say, a 3×3 square, three smaller squares must already fit: the one ending just above, the one just to the left, and the one on the diagonal. The biggest square we can extend is limited by the smallest of those three, so dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) when the cell is a 1.

Cells on the first row or first column can only ever be a 1×1 square, so they are just set to 1 when they hold a 1. A 0 cell stays 0 because no square can end there.

Taking the minimum works because a square needs every one of those three neighbouring squares to be at least that big; one short corner caps the whole thing. We track the largest side seen and return its area (side × side).

Example: in the sample grid the block of 1s in the middle lets some corner reach dp = 2, so the side is 2 and the answer is 2 × 2 = 4.

Time: O(m·n) Space: O(m·n)