⚡Flashcard Drill➔
NeetCode #727LC-221Medium2-D Dynamic Programming
← Back to All Problems

#727 · #221 · Maximal Square(最大正方形)

📌 Problem Statement & Constraints

Given an m x n binary matrix of 0 and 1, find the area of the largest square containing only 1s. Constraints: 1 <= m, n <= 300, and matrix[i][j] is 0 or 1.

💡 Core Algorithmic Approaches

  1. dp[i][j] is the side length of the largest all-ones square whose bottom-right corner is (i, j).
  2. If matrix[i][j] == 1, then dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
  3. The minimum of the three neighbours is the largest square that can extend one cell down-right.
  4. The answer is the square of the largest dp value.

💻 Benchmark Python3 Implementation

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [0] * (n + 1)
        best = 0
        for i in range(1, m + 1):
            prev = 0                   # dp[i-1][j-1] from the previous row
            for j in range(1, n + 1):
                tmp = dp[j]            # dp[i-1][j] before overwrite
                if matrix[i - 1][j - 1] == "1":
                    dp[j] = 1 + min(dp[j], dp[j - 1], prev)
                    best = max(best, dp[j])
                else:
                    dp[j] = 0
                prev = tmp
        return best * best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): every cell is visited once.
💾 Space Complexity
O(n): a single row plus one saved diagonal value.

⚠️ Interview Pitfalls & Follow-ups

  • Comparing against the integer 1: the input is a character matrix, so the comparison uses the string 1.
  • Forgetting to reset dp[j] to 0 on a zero cell: otherwise the previous row's value leaks through.
  • Using max instead of min: the square is limited by its smallest neighbour.
  • Returning the side length instead of the area: the answer is best * best.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems