Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtwo-dimensional-dp

Maximal Square

Problem (restated)

Binary matrix of ‘0’/‘1’. Return the area of the largest square containing only 1s.

Intuition

dp[i][j] = max square side ending at (i-1,j-1). If cell is 1: 1+min(up, left, diagonal).

Approaches

Side-length DP on grid

Tested only

Time O(mn)Space O(mn)

Idea. Only a cell of ‘1’ can extend; bottleneck is the min of three neighbors.

Walkthrough. A 2×2 block of ones gives side 2 → area 4.

Trade-offs. Return best*best (area). Rolling 1D row reduces space to O(n).

Solution

export function maximalSquare(matrix: string[][]): number {
  const m = matrix.length;
  const n = matrix[0]!.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  let best = 0;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (matrix[i - 1]![j - 1] === "1") {
        dp[i]![j] =
          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;
}

export function maximalSquare(matrix: string[][]): number {
  const m = matrix.length;
  const n = matrix[0]!.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  let best = 0;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (matrix[i - 1]![j - 1] === "1") {
        dp[i]![j] =
          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;
}

Template connection

Grid DP where state is geometric size, not path count.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?