Square Dynamic Programming: Matrix & Grid Problems

The Square DP pattern deals with problems involving square regions inside a matrix.

Unlike regular Grid DP that focuses on paths and movement, Square DP focuses on:

“What is the largest or total square satisfying certain conditions?”

The key observation is:

A square of size k exists only if its neighboring smaller squares also exist.

Most Square DP problems use local information from:

top
left
top-left (diagonal)

to determine the answer for the current cell.

Focus on recognizing:

“Find squares/submatrices satisfying a condition.”

Pattern Table

Pattern	Typical Question Types	Keywords in Question	Why Use / Notes
Maximal Square	Largest valid square	largest square, all 1s	Build square sizes using neighboring cells
Count Square Submatrices	Count all valid squares	count squares, all 1s	Every cell contributes multiple squares
Largest Square of 1s	Maximum square area	binary matrix, square	Same recurrence as Maximal Square
Largest Zero Square	Largest square satisfying condition	zeros, square	Modify recurrence condition
Largest Border Square	Border-only validation	border, square	Additional prefix preprocessing
Largest Plus Sign	Symmetric expansion	plus sign, largest order	Four directional DP
Largest X Shape	Diagonal expansion	X shape, diagonals	Diagonal DP transitions
Maximum Rectangle → Square	Square variations	rectangle, square	Extend histogram techniques

Mini Notes / Tips

### Tips

- Square DP almost always uses dp[i][j].
- Define:
  dp[i][j] = largest square ending at (i, j).
- The diagonal (top-left) neighbor is the key difference from path DP.
- Most problems are solved bottom-up.
- Binary matrices are the most common input.
- Area is often obtained by squaring the side length.
- Prefix sums may help validate larger squares efficiently.

Square DP – Detection & Usage Guide

1. Maximal Square – Very Common

Maximal Square

Largest square of 1s in a binary matrix.

dp[i][j] = side of the largest all-1 square ending at (i,j). If the cell is 1, dp[i][j] = 1 + min(top, left, diagonal) — all three neighbours must support the corner. Answer = max side; area is its square. O(rows·cols).

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[i][j] = side of largest square ending at (i,j)
                      
                        2
                        if matrix[i][j] == 0: dp[i][j] = 0
                      
                        3
                        else dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
                      
                        4
                        answer = max(dp)² (area)

When to use / Detection cues:

Input structure: Binary matrix.
Question keywords: largest square, all 1s.
Problem hints: Find the maximum square area.
Why it works: A larger square exists only if three neighboring squares exist.

State Definition:

dp[i][j]
=
side length of the largest square
ending at (i, j)

Transition:

if matrix[i][j] == 1:

    dp[i][j] =
        1 +
        min(
            dp[i-1][j],
            dp[i][j-1],
            dp[i-1][j-1]
        )

else:

    dp[i][j] = 0

Typical questions:

Maximal Square
Largest Square of 1s

Mental trigger:

“Largest square of 1s” → Square DP.

public int maximalSquare(char[][] matrix) {
    if (matrix == null || matrix.length == 0) return 0;
    int m = matrix.length, n = matrix[0].length;
    int[][] dp = new int[m][n];
    int maxSide = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '1') {
                if (i == 0 || j == 0) dp[i][j] = 1;
                else dp[i][j] = 1 + Math.min(dp[i - 1][j],
                    Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
    }
    return maxSide * maxSide;
}

def maximal_square(matrix):
    if not matrix or not matrix[0]:
        return 0
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    max_side = 0
    for i in range(m):
        for j in range(n):
            if matrix[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])
                max_side = max(max_side, dp[i][j])
    return max_side * max_side

int maximalSquare(vector<vector<char>>& matrix) {
    if (matrix.empty() || matrix[0].empty()) return 0;
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    int maxSide = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '1') {
                if (i == 0 || 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]});
                maxSide = max(maxSide, dp[i][j]);
            }
        }
    }
    return maxSide * maxSide;
}

function maximalSquare(matrix) {
  if (!matrix.length || !matrix[0].length) return 0;
  const m = matrix.length, n = matrix[0].length;
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));
  let maxSide = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (matrix[i][j] === '1') {
        if (i === 0 || j === 0) dp[i][j] = 1;
        else dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
        maxSide = Math.max(maxSide, dp[i][j]);
      }
    }
  }
  return maxSide * maxSide;
}

2. Count Square Submatrices with All Ones – Very Common

Count Square Submatrices

Count every square submatrix made of 1s.

Run the maximal-square recurrence; dp[i][j] = largest square ending at (i,j). Every cell ending with side k contributes one k×k square, so the total count is the sum of all dp values. O(mn) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])  if 1
                      
                        2
                        dp[i][j] = 0  if 0
                      
                        3
                        answer = sum(dp)

When to use / Detection cues:

Input structure: Binary matrix.
Question keywords: count squares, total squares.
Problem hints: Count every valid square.
Why it works: Each cell contributes all square sizes ending there.

Formula:

answer += dp[i][j]

because:

dp[i][j] = k

means

1×1
2×2
...
k×k

all exist.

Typical questions:

Count Square Submatrices with All Ones

Mental trigger:

“Count all valid squares” → Square DP.

public int countSquares(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int[][] dp = new int[m][n];
    int total = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 1) {
                if (i == 0 || j == 0) dp[i][j] = 1;
                else dp[i][j] = 1 + Math.min(dp[i - 1][j],
                    Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
                total += dp[i][j];
            }
        }
    }
    return total;
}

def count_squares(matrix):
    if not matrix or not matrix[0]:
        return 0
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    total = 0
    for i in range(m):
        for j in range(n):
            if matrix[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])
                total += dp[i][j]
    return total

int countSquares(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    int total = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 1) {
                if (i == 0 || 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]});
                total += dp[i][j];
            }
        }
    }
    return total;
}

function countSquares(matrix) {
  const m = matrix.length, n = matrix[0].length;
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));
  let total = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (matrix[i][j] === 1) {
        if (i === 0 || j === 0) dp[i][j] = 1;
        else dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
        total += dp[i][j];
      }
    }
  }
  return total;
}

3. Largest Square of Zeros – Common

Largest Square of Zeros

Biggest square submatrix consisting only of 0s.

Same recurrence as maximal square, but the condition flips: dp[i][j] = 1 + min(neighbors) only when matrix[i][j] == 0. O(mn) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        if matrix[i][j] == 0:
                      
                        2
                          dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
                      
                        3
                        else: dp[i][j] = 0
                      
                        4
                        answer = max(dp)

When to use / Detection cues:

Input structure: Binary matrix.
Question keywords: zeros, square.
Problem hints: Same logic as maximal square.
Why it works: Simply invert the condition.

Transition:

if matrix[i][j] == 0:

    dp[i][j] =
        1 +
        min(
            top,
            left,
            diagonal
        )

Typical questions:

Largest Square of Zeros

Mental trigger:

“Square satisfying another condition” → Modified Square DP.

public int largestZeroSquare(char[][] matrix) {
    if (matrix == null || matrix.length == 0) return 0;
    int m = matrix.length, n = matrix[0].length;
    int[][] dp = new int[m][n];
    int maxSide = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '0') {
                if (i == 0 || j == 0) dp[i][j] = 1;
                else dp[i][j] = 1 + Math.min(dp[i - 1][j],
                    Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
    }
    return maxSide * maxSide;
}

def largest_zero_square(matrix):
    if not matrix or not matrix[0]:
        return 0
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    max_side = 0
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == '0':
                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])
                max_side = max(max_side, dp[i][j])
    return max_side * max_side

int largestZeroSquare(vector<vector<char>>& matrix) {
    if (matrix.empty() || matrix[0].empty()) return 0;
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    int maxSide = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '0') {
                if (i == 0 || 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]});
                maxSide = max(maxSide, dp[i][j]);
            }
        }
    }
    return maxSide * maxSide;
}

function largestZeroSquare(matrix) {
  if (!matrix.length || !matrix[0].length) return 0;
  const m = matrix.length, n = matrix[0].length;
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));
  let maxSide = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (matrix[i][j] === '0') {
        if (i === 0 || j === 0) dp[i][j] = 1;
        else dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
        maxSide = Math.max(maxSide, dp[i][j]);
      }
    }
  }
  return maxSide * maxSide;
}

4. Largest 1-Bordered Square – Common

Largest 1-Bordered Square

Square whose entire border is made of 1s (inside may be 0).

Precompute left/up prefix counts of consecutive 1s. A square of side k is 1-bordered if its top and bottom rows have ≥k consecutive 1s and its left/right columns have ≥k consecutive 1s. O(mn·min(m,n)) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        left[i][j] = consecutive 1s to the left
                      
                        2
                        up[i][j] = consecutive 1s above
                      
                        3
                        for side k from min(m,n) downto 1:
                      
                        4
                          check 4 borders have length >= k
                      
                        5
                        return first k that fits

When to use / Detection cues:

Input structure: Binary matrix.
Question keywords: border, perimeter.
Problem hints: Only edges matter.
Why it works: Prefix preprocessing validates borders efficiently.

Typical questions:

Largest 1-Bordered Square

Mental trigger:

“Only borders matter” → Prefix + Square DP.

5. Largest Plus Sign – Common

Largest Plus Sign

Biggest '+' shape (equal arms) of 1s in a grid.

For each cell compute arm lengths in 4 directions (up/down/left/right consecutive 1s). The plus order at a cell = 1 + min of the four arm lengths. O(mn) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        up[i][j], down[i][j], left[i][j], right[i][j] = arm lengths
                      
                        2
                        order[i][j] = 1 + min(up,down,left,right)
                      
                        3
                        answer = max(order)

When to use / Detection cues:

Input structure: Grid.
Question keywords: plus sign, order.
Problem hints: Need expansion in four directions.
Why it works: DP stores arm lengths.

Maintain:

left
right
up
down

Typical questions:

Largest Plus Sign

Mental trigger:

“Expand equally in four directions” → Directional DP.

6. Largest X Shape – Moderate

Largest X Shape

Biggest 'X' (both diagonals) of 1s in a grid.

Compute diagonal arm lengths in all four diagonal directions. The X order at a cell = 1 + min of the four diagonal arms. Like plus sign but along diagonals. O(mn) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        diag1up/down, diag2up/down = diagonal arm lengths
                      
                        2
                        order[i][j] = 1 + min(four diagonal arms)
                      
                        3
                        answer = max(order)

When to use / Detection cues:

Input structure: Matrix.
Question keywords: X shape, diagonals.
Problem hints: Expansion occurs diagonally.
Why it works: Track diagonal lengths.

Maintain:

↖
↗
↙
↘

directional DP.

Typical questions:

Largest X of 1s

Mental trigger:

“Diagonal symmetry” → Diagonal DP.

7. Maximum Rectangle to Square Variants – Moderate

Maximum Rectangle to Square

Largest square that fits inside the maximal rectangle of 1s.

Find the maximal rectangle (histogram / row-wise DP) to get its height h and width w. The largest square that fits has side = min(h, w). Combine rectangle DP with the min-side rule. O(mn) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        for each row: update heights[] (histogram of 1s)
                      
                        2
                        find maximal rectangle in histogram -> (h, w)
                      
                        3
                        largest square side = min(h, w)

When to use / Detection cues:

Input structure: Matrix.
Question keywords: rectangle, square.
Problem hints: Extend histogram methods to square constraints.
Why it works: Restrict rectangle dimensions to squares.

Typical questions:

Largest Square in Histogram Variants
Square-based area optimization

Mental trigger:

“Rectangle problem with square restrictions” → Hybrid DP.

How to Identify Square DP

Ask these questions:

Is the input a matrix/grid?

Is the question asking about squares or square areas?

Does the current answer depend on:

top
left
top-left

neighbors?

Are you finding the largest square or counting squares?

If most answers are yes,

Think Square DP.

Classic Square DP Template

for i from 0 to rows-1:

    for j from 0 to cols-1:

        if matrix[i][j] satisfies condition:

            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]
                    )

        else:

            dp[i][j] = 0

Recognition Cheat Sheet

If you see…	Think…
Largest square of 1s	Maximal Square
Count all square submatrices	Count Squares
Largest square of 0s	Modified Square DP
Border-only square validation	Border Square
Largest plus sign	Directional DP
Largest X shape	Diagonal DP
Rectangle problem with square rules	Hybrid Square DP

Square DP vs Grid DP

Feature	Grid DP	Square DP
Goal	Paths / movement	Squares / submatrices
State	Ways/cost to reach cell	Largest square ending at cell
Transition	Top / Left	Top + Left + Diagonal
Common Problems	Unique Paths	Maximal Square
Typical Answer	Path count/cost	Side length or area

⚠️ Animation & Content Notice

Square DP

Pattern Table

Mini Notes / Tips

Square DP – Detection & Usage Guide

1. Maximal Square – Very Common

⚠️ Animation & Content Notice

Maximal Square

2. Count Square Submatrices with All Ones – Very Common

⚠️ Animation & Content Notice

Count Square Submatrices

3. Largest Square of Zeros – Common

⚠️ Animation & Content Notice

Largest Square of Zeros

4. Largest 1-Bordered Square – Common

⚠️ Animation & Content Notice

Largest 1-Bordered Square

5. Largest Plus Sign – Common

⚠️ Animation & Content Notice

Largest Plus Sign

6. Largest X Shape – Moderate

⚠️ Animation & Content Notice

Largest X Shape

7. Maximum Rectangle to Square Variants – Moderate

⚠️ Animation & Content Notice

Maximum Rectangle to Square

How to Identify Square DP

Classic Square DP Template

Recognition Cheat Sheet

Square DP vs Grid DP

Premium Content

My Private Notes

Earn Premium with Referrals

Pattern Table

Mini Notes / Tips

Square DP – Detection & Usage Guide

1. Maximal Square – Very Common

Maximal Square

2. Count Square Submatrices with All Ones – Very Common

Count Square Submatrices

3. Largest Square of Zeros – Common

Largest Square of Zeros

4. Largest 1-Bordered Square – Common

Largest 1-Bordered Square

5. Largest Plus Sign – Common

Largest Plus Sign

6. Largest X Shape – Moderate

Largest X Shape

7. Maximum Rectangle to Square Variants – Moderate

Maximum Rectangle to Square

How to Identify Square DP

Classic Square DP Template

Recognition Cheat Sheet

Square DP vs Grid DP

Premium Content

My Private Notes