Maximal Square

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Given an m × n grid of '0' and '1' characters, return the area of the largest square that contains only '1's. The square's sides are parallel to the grid. If the grid has no '1' at all, return 0.

    A 2D dynamic-programming question whose whole difficulty is choosing the right state. Once you define it, the recurrence is one line. Original problem: LeetCode 221.

    Example

    The green 3 × 3 block in the top-right corner is the largest all-1 square, so the answer is 9.
    The green 3 × 3 block in the top-right corner is the largest all-1 square, so the answer is 9.
    Input:  [["1","0","1","1","1"],
             ["1","1","1","1","1"],
             ["0","1","1","1","1"],
             ["1","1","0","1","1"]]
    Output: 9         # side 3
    Input:  [["0","1"], ["1","0"]]   ->  1
    Input:  [["0"]]                  ->  0

    Constraints (assumed)

    • 1 ≤ m, n ≤ 300.

    What this question tests

    • Defining a DP state on the bottom-right corner of a square.
    • Seeing why the answer depends on three neighbours, not two.
    • Reducing memory to one row; returning the area, not the side.

    Questions to ask first

    1. Area or side length? (Here: area.)
    2. Are the cells characters or integers? (Here: the characters '0' and '1'.)
    3. Square only, or any rectangle? (Here: square. The rectangle version is a harder follow-up.)
    4. May I modify the grid to store DP values in place?