Largest All-Ones Square in a Grid

medium dp grid

Problem

Given an m × n binary grid (cells are 0 or 1), return the area of the largest square containing only 1s.

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;
}

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