What is the brute force approach and complexity for Maximal Square?

Try every top-left corner and every side, and check every cell of each square with time complexity O(M · N · min(M, N)³) and space complexity O(1).

What is the optimal approach and complexity for Maximal Square?

dp[r][c] = 1 + min(top, left, top-left) on a 1; keep one row and the diagonal with optimal time complexity O(M · N) and space complexity O(N).

How do you identify the pattern for Maximal Square?

Look for key signals in the prompt: "largest square" indicates The answer is a square, not any rectangle. A square grows one ring at a time, so its side can be tracked in a table.; "filled only with 1s" indicates A `'0'` cell stops every square that would cover it, so a 0 resets its dp value.; "return its area" indicates The table tracks the side. The answer is side × side..

Maximal Square

Medium·LeetCode #221Basic Anchor

LeetCode

Jump:

30-Second Mental ModelDP — Grid, Squares and shapes (dp[r][c] = 1 + min(top, left, top-left))

Complexity:O(M · N · min(M, N)³)→O(M · N)

Key Insight

Let dp[r][c] be the side of the biggest all-ones square whose bottom-right corner is (r, c). If the cell is '1', the square can only be as big as its weakest neighbour allows: dp[r][c] = 1 + min(top, left, top-left). Each cell only reads three neighbours, so we only need the previous row.

Core Validity Invariant

A square of side s can end at (r, c) only if the top, left and top-left cells each end a square of side s − 1. So dp[r][c] is 1 plus the smallest of those three values.

Problem

You get a grid made of '0' and '1' characters. Find the biggest square that is filled only with '1' cells.

Return the area of that square, not its side length. For example, a 2 × 2 square of ones has area 4.

Input

A grid matrix with m rows and n columns. Each cell is the character '0' or '1'.

Output

The area of the largest all-'1' square. If there is no '1' at all, the answer is 0.

Example 1

Input: matrix = [["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]]

Output: 4

The biggest square of ones is 2 × 2, so its area is 4. The block at rows 1–2 and columns 3–4 is all ones.

Example 2

Input: matrix = [["0","1"], ["1","0"]]

Output: 1

No 2 × 2 block is all ones. A single '1' is a square of side 1, so the area is 1.

Example 3

Input: matrix = [["0"]]

Output: 0

There is no '1' at all, so no square counts.

Constraints

• 1 ≤ m, n ≤ 300
• Each cell is `'0'` or `'1'`.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
A square with side k and bottom-right corner (r, c) needs which cells to be all ones?
2.
If I know the biggest square that ends at the cell above, and the one that ends at the cell to the left, what limits the square that ends here?
3.
Can a square end at (r, c) if the cell at (r − 1, c − 1) is 0? What does that tell me?
4.
Is the output a side length or an area? Read the output line again.
5.
Can I check a square without reading all of its cells, if I already know the squares around it?

Brute force approach

Idea

A square is fixed by its top-left corner and its side k. For each one, check all k × k cells. If they are all '1', the square counts, and we keep the largest area. Every cell is read again by every square that covers it.

Thinking process

1
Take rows 1–2 and columns 3–4 of example 1. That is a 2 × 2 block of ones with top-left corner (1, 3).
2
From (1, 3), try side 1: one cell, it is '1', so area 1 counts.
3
Try side 2 from (1, 3): four cells, all '1', so area 4 counts.
4
Try side 3 from (1, 3): it needs column 5, which does not exist. Stop and move to the next corner.
5
Do this for every top-left corner and keep the largest area. For example 1 the answer is 4.

Visual

Each step is one square: its top-left corner and its side k. Blue = a cell read for the first time. Orange = a cell an earlier square already read (repeated work). Red = a 0 inside the square. Grey = a 0 in the matrix. Purple = the best square.

Brute force: check every squarematrix (3 × 4)step 1/22

matrix

State

squares checked: 0
cells read: 0
best: 0

Start: no square checked yet

The brute force checks every square: every top-left corner (r, c) and every side k that fits. For each one it reads all k × k cells, even the ones earlier squares already read.

Code & Implementation

brute.cpp

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int best = 0;
        // Every top-left corner, and every side k that fits from there.
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                for (int k = 1; r + k <= m && c + k <= n; k++) {
                    // Check every cell of the k x k square (no shortcut).
                    bool allOnes = true;
                    for (int i = r; i < r + k; i++)
                        for (int j = c; j < c + k; j++)
                            if (matrix[i][j] != '1') allOnes = false;
                    if (allOnes) best = max(best, k * k);   // keep the area
                }
        return best;
    }
};

Complexity

Time O(M · N · min(M, N)³)Space O(1)

M is the number of rows and N the number of columns. There are M · N top-left corners. From each corner the side goes from 1 up to min(M, N), and checking a side-k square reads k² cells. Summing k² up to that limit gives about min(M, N)³ / 3 per corner, so the total is about M · N · min(M, N)³ / 3. With M = N = 300 this is far too slow.

Better approach

Why brute force is slow

Each square is checked from scratch, one cell at a time, even when a bigger square contains it.

What repeated work are we doing?

The same cells are read by many squares. A cell near the middle of the grid is read by every square that covers it.

What information can we reuse?

A 2-D prefix-sum table. After one pass over the grid, the number of ones in any rectangle takes four lookups.

New approach

Idea

Build a table P once, where P[i][j] is the number of '1's above and to the left of cell (i, j). Then the number of ones in any square is four lookups. A square is all ones exactly when that count equals side × side.

Thinking process

1
Brute force reads every cell of a square, and big squares share cells with small ones. A count table makes each check cost the same, whatever the size.
2
In example 1, the square with top-left (1, 3) and side 2 has 4 ones. Lookup: P[3][5] − P[1][5] − P[3][3] + P[1][3] = 11 − 2 − 7 + 2 = 4.
3
The count is 4 and side × side is 2 × 2 = 4, so every cell is '1'. The square is valid.
4
A square that has a 0 inside gives a smaller count than side × side, so it is not valid.
5
We still try every corner and every side, so the work is about M · N · min(M, N) lookups.

Code & Implementation

better.cpp

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        // P[i][j] = number of '1's in rows 0..i-1 and columns 0..j-1 (2-D prefix sums).
        vector<vector<int>> P(m + 1, vector<int>(n + 1, 0));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                P[i + 1][j + 1] = P[i][j + 1] + P[i + 1][j] - P[i][j] + (matrix[i][j] == '1');

        int best = 0;
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                for (int k = 1; r + k <= m && c + k <= n; k++) {
                    // Count the ones in the k x k square with top-left (r, c) in O(1).
                    int ones = P[r + k][c + k] - P[r][c + k] - P[r + k][c] + P[r][c];
                    if (ones == k * k) best = max(best, k * k);   // all ones: keep the area
                }
        return best;
    }
};

Complexity

Time O(M · N · min(M, N))Space O(M · N)

There are M · N top-left corners and at most min(M, N) sides for each, and each check is O(1). The prefix table holds (M + 1) · (N + 1) numbers. It is faster than brute force, but the next approach needs no table at all.

Optimized approach

Idea

Start from brute force

Brute force checks each square from scratch, cell by cell. But a square ending at a corner is built from the squares that end at its three neighbours, so those answers can be reused.

Find the repeated work

A side-3 square ending at (r, c) contains a side-2 square ending at the same corner. Brute force finds the small square again for every size, and it reads the same cells again every time.

Define the state — what variables do I need?

dp[r][c]: The side of the biggest all-ones square whose bottom-right corner is (r, c). It is 0 when the cell is `'0'`.
row: The current row of dp, as one array of N + 1 values. Column 0 is a fake column that stays 0.
diag: dp[r − 1][c − 1], saved before the value at that column is overwritten.
best: The largest side found so far.

Define validity

A square of side s can end at (r, c) only if the top, left and top-left cells each end a square of side s − 1. So dp[r][c] is 1 plus the smallest of those three values.

Define the transitions — when does each pointer move, and why is it safe?

The cell is `'0'`

dp[r][c] = 0

No square can end on a 0 cell.

The cell is `'1'`

dp[r][c] = 1 + min(top, left, top-left)

The square needs all three neighbours to hold a square of one less side. The smallest neighbour is the limit.

After each cell

best = max(best, dp[r][c])

The biggest square can end anywhere in the grid, not only at the bottom-right corner.

At the start of each row

diag = 0, then diag = the old top value after each cell

The next cell needs the old top-left value, which the current row is about to overwrite.

What does the current window add to the answer?

Each '1' cell adds one candidate: the biggest square that ends there. The largest candidate over all cells is the biggest square in the grid.

Code & Implementation

optimal.cpp

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        // dp[c] = side of the largest all-ones square whose bottom-right corner is (row, c - 1).
        // Columns are 1-based so dp[0] is a fake column that stays 0.
        vector<int> dp(n + 1, 0);
        int best = 0;
        for (int r = 0; r < m; r++) {
            int diag = 0;                       // dp[r-1][c-1], saved before dp[c-1] is overwritten
            for (int c = 1; c <= n; c++) {
                int above = dp[c];              // dp[r-1][c]: still last row's value
                if (matrix[r][c - 1] == '1')
                    dp[c] = 1 + min({above, dp[c - 1], diag});  // dp[c-1] is already this row's value
                else
                    dp[c] = 0;                  // a 0 cell ends every square here
                diag = above;
                best = max(best, dp[c]);
            }
        }
        return best * best;                     // the answer is the area, not the side
    }
};

Complexity

Time O(M · N)Space O(N)

M is the number of rows and N the number of columns. Each cell does one min and one add. The code keeps one row of N + 1 values and one saved diagonal value, so the extra space is O(N), not O(M · N).

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Try every top-left corner and every side, and check every cell of each square	O(M · N · min(M, N)³)	O(1)
Better	Count the ones in any square with a prefix-sum table; the square is all ones when the count is k × k	O(M · N · min(M, N))	O(M · N)
Optimal	dp[r][c] = 1 + min(top, left, top-left) on a 1; keep one row and the diagonal	O(M · N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“largest square”The answer is a square, not any rectangle. A square grows one ring at a time, so its side can be tracked in a table.
“filled only with 1s”A `'0'` cell stops every square that would cover it, so a 0 resets its dp value.
“return its area”The table tracks the side. The answer is side × side.

2-D grid+square that ends at each corner+min of three neighbours plus 1→DP — Grid, Squares and shapes (dp[r][c] = 1 + min(top, left, top-left))

This is the anchor of Squares and shapes. At each cell the only question is how far a square can reach up and to the left, and the answer is the minimum of the three neighbours. Count Square Submatrices with All Ones uses the same table, but it adds up every cell instead of taking the maximum.

Don't make this mistake

Pattern confusion: using only the top and left neighbours

✗ dp[r][c] = 1 + min(dp[r-1][c], dp[r][c-1]);

✓ dp[r][c] = 1 + min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]);

The top-left cell can be '0' even when the top and left are both '1'. On the grid [["0","1"], ["1","1"]] the bottom-right cell has top 1 and left 1, so the wrong rule gives side 2 (area 4). But the 2 × 2 square would need the top-left cell, which is 0. The true answer is area 1.

Returning the side instead of the area

✗ return best;

✓ return best * best;

The question asks for the area. On example 1 the biggest side is 2, so the wrong code returns 2 instead of 4.

One-row version forgets to reset a 0 cell

✗ if (matrix[r][c-1] == '1') dp[c] = 1 + min({above, dp[c-1], diag});

✓ dp[c] = matrix[r][c-1] == '1' ? 1 + min({above, dp[c-1], diag}) : 0;

A '0' cell must set dp to 0. Without that, the cell keeps the value from the row above. On the grid [["1","1"], ["0","1"]] the cell below the first '1' keeps a stale 1, so the bottom-right cell wrongly gets side 2 (area 4). The answer is 1, because the 2 × 2 square has a '0' in it.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Grid translate into production architectures and low-level memory mechanics.

LLD Architecture