Log inSign up
mediumLeetCodeNot Started

Maximal Square

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example 1 · Standard 4x5 Matrix:

Input: matrix = [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ]
Output: 4
Explanation: The maximal square has side length 2 (area = 2 * 2 = 4).

Example 2 · 2x2 Matrix with Single 1:

Input: matrix = [["0","1"],["1","0"]]
Output: 1
Explanation: Largest square is 1x1 with area 1.

Example 3 · All Zero Matrix:

Input: matrix = [["0"]]
Output: 0
Explanation: No 1s exist, area is 0.

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] is 0 or 1.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • 2D matrix indexing and boundary checking
  • Dynamic Programming state formulation on grids
  • Rolling 1D array space optimization

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3-neighbor minimum DP recurrence for geometric squares.
  • Understand why a square shape requires checking the diagonal top-left neighbor in addition to top and left.
  • Compress 2D grid DP into a 1D rolling array with a scalar diagonal register.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Maximal RectangleCount Square Submatrices with All OnesMinimum Path Sum

1. Check All Subsquares (Brute Force)

Intuition

For every cell (r, c) where matrix[r][c] == 1, try square side length k = 1, 2, ... Check whether the k x k square with top-left at (r, c) contains exclusively 1s. Stop when an all-1 square cannot be formed.

When to apply: Use to understand the maximal square definition.

Brute Force Subsquare Search Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 0, 1, 1, 1, 1, 1, 1, 1]
Current operationSTEP 1 OF 6
Matrix: [['1','0','1'], ['1','1','1'], ['1','1','1']]
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
1
↑ k=1
0
1
r1
1
1
1
r2
1
1
1
Variables at this step
maxSide
1
Check / comparison
(0,1)='0'
Decision / next transition
At (0,0), max side is 1.
Why this step matters

Matrix: [[1,0,1], [1,1,1], [1,1,1]]. Cell (0,0)=1: 1x1 valid. 2x2 square includes (0,1)=0 (invalid).

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int maximalSquare(char[][] matrix) {
4 if (matrix == null || matrix.length == 0) return 0;
5 int m = matrix.length, n = matrix[0].length;
6 int maxSide = 0;
7
8 for (int r = 0; r < m; r++) {
9 for (int c = 0; c < n; c++) {
10 if (matrix[r][c] == '1') {
11 int side = 1;
12 boolean flag = true;
13 while (r + side < m && c + side < n && flag) {
14 for (int i = r; i <= r + side; i++) {
15 if (matrix[i][c + side] == '0') { flag = false; break; }
16 }
17 for (int j = c; j <= c + side; j++) {
18 if (matrix[r + side][j] == '0') { flag = false; break; }
19 }
20 if (flag) side++;
21 }
22 maxSide = Math.max(maxSide, side);
23 }
24 }
25 }
26 return maxSide * maxSide;
27 }
28 }
29
30 public static void main(String[] args) {
31 Solution sol = new Solution();
32 char[][] matrix = {
33 {'1', '0', '1'},
34 {'1', '1', '1'},
35 {'1', '1', '1'}
36 };
37 System.out.println("Maximal Square Area: " + sol.maximalSquare(matrix));
38 }
39}

Time & Space Complexity

  • Time complexity: O((m * n) * min(m, n)^2) — For each of m*n cells, verifying squares up to min(m, n) size takes quadratic operations in the square side.
  • Space complexity: O(1) — No extra memory is used.

Why Brute Force Doesn't Scale:

For a 300x300 matrix, 3004 exceeds 8.1 billion checks.

1D DP processes 300x300 in 90,000 operations (< 2ms) using only 301 integers of memory.

2. 2D Dynamic Programming (Optimal Time)

Intuition

If matrix[i-1][j-1] == 1, then dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. The side of the square ending at (i, j) is bounded by the smallest of its three adjacent top/left/diagonal squares.

When to apply: Use as the intuitive tabular DP formulation.

2D DP Table Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 0, 1, 1, 1, 1, 1, 1, 1]
Current operationSTEP 1 OF 6
DP table initialized with size 4x4 of zeroes
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
1
↑ dp[1][1]=1
0
1
r1
1
1
1
r2
1
1
1
Variables at this step
row1
[0,1,0,1]
Check / comparison
Row 1 initialized.
Decision / next transition
dp[1] = [0, 1, 0, 1].
Why this step matters

DP table initialized with size 4x4 of zeroes. Row 1: dp[1][1]=1 (from 1), dp[1][2]=0 (0), dp[1][3]=1 (1).

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int maximalSquare(char[][] matrix) {
4 if (matrix == null || matrix.length == 0) return 0;
5 int m = matrix.length, n = matrix[0].length;
6 int[][] dp = new int[m + 1][n + 1];
7 int maxSide = 0;
8
9 for (int r = 1; r <= m; r++) {
10 for (int c = 1; c <= n; c++) {
11 if (matrix[r - 1][c - 1] == '1') {
12 dp[r][c] = Math.min(dp[r - 1][c], Math.min(dp[r][c - 1], dp[r - 1][c - 1])) + 1;
13 maxSide = Math.max(maxSide, dp[r][c]);
14 }
15 }
16 }
17 return maxSide * maxSide;
18 }
19 }
20
21 public static void main(String[] args) {
22 Solution sol = new Solution();
23 char[][] matrix = {
24 {'1', '0', '1'},
25 {'1', '1', '1'},
26 {'1', '1', '1'}
27 };
28 System.out.println("Maximal Square Area: " + sol.maximalSquare(matrix));
29 }
30}

Time & Space Complexity

  • Time complexity: O(m * n) — Single pass over the (m+1) x (n+1) DP table.
  • Space complexity: O(m * n) — DP table of size (m+1) x (n+1).

3. 1D Space-Optimized Dynamic Programming (Optimal & Standard)

Intuition

1. Maintain 1D array dp of size n + 1. 2. For each row: maintain prev holding dp[r-1][c-1]. 3. For each col c: temp = dp[c]; if matrix[r-1][c-1] == 1, dp[c] = min(dp[c], dp[c-1], prev) + 1; else dp[c] = 0; prev = temp. 4. Return maxSide * maxSide.

When to apply: Use as the optimal standard to conserve memory when m or n is large.

1D Space-Optimized DP Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 0, 1, 1, 1, 1, 1, 1, 1]
Current operationSTEP 1 OF 6
Initialize dp array of size 4: [0, 0, 0, 0]
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
1
↑ Row 0
0
1
r1
1
1
1
r2
1
1
1
Variables at this step
dp
[0,0,0,0]
Check / comparison
Base setup.
Decision / next transition
dp=[0, 0, 0, 0].
Why this step matters

Initialize dp array of size 4: [0, 0, 0, 0]. maxSide = 0.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int maximalSquare(char[][] matrix) {
4 if (matrix == null || matrix.length == 0) return 0;
5 int m = matrix.length, n = matrix[0].length;
6 int[] dp = new int[n + 1];
7 int maxSide = 0, prev = 0;
8
9 for (int r = 1; r <= m; r++) {
10 prev = 0;
11 for (int c = 1; c <= n; c++) {
12 int temp = dp[c];
13 if (matrix[r - 1][c - 1] == '1') {
14 dp[c] = Math.min(dp[c], Math.min(dp[c - 1], prev)) + 1;
15 maxSide = Math.max(maxSide, dp[c]);
16 } else {
17 dp[c] = 0;
18 }
19 prev = temp;
20 }
21 }
22 return maxSide * maxSide;
23 }
24 }
25
26 public static void main(String[] args) {
27 Solution sol = new Solution();
28 char[][] matrix = {
29 {'1', '0', '1'},
30 {'1', '1', '1'},
31 {'1', '1', '1'}
32 };
33 System.out.println("Maximal Square Area: " + sol.maximalSquare(matrix));
34 }
35}

Time & Space Complexity

  • Time complexity: O(m * n) — Single pass over the grid, visiting each element once.
  • Space complexity: O(n) — 1D array of length n + 1.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Expanding Square ValidationO((M * N) * min(M, N)^2)O(1)For every cell with 1, expand square side length k = 1, 2, 3... and verify if all perimeter cells are 1.Repeated cell verification loops.
2.Better — 2D Dynamic Programming TableO(M * N)O(M * N)Allocate (m+1) x (n+1) DP table. dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) if matrix[i-1][j-1] == '1'.2D table allocations.
3.Optimal — 1D Space-Optimized Dynamic ProgrammingOptimalO(M * N)O(N)Compress 2D table into a 1D row array dp[n+1]. Keep a variable prev storing dp[i-1][j-1] before it gets overwritten.None; theoretical optimum.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • All zero matrix — Returns 0.
  • Single element matrix [['1']] — Returns 1.
  • Long single row or column — Max square cannot exceed 1x1, returns 1 if any 1 present.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clearly distinguish between Maximal Square (O(M*N) DP) vs Maximal Rectangle (O(M*N) Monotonic Stack).
  2. Explain why the padding dimension (m+1, n+1) simplifies boundary checks.
  3. Walk through the space compression transition from 2D table to 1D vector + prev diagonal variable.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Maximal Square?

2.Why is the brute force approach suboptimal for large inputs in Maximal Square?

3.Which data structure or technique enables the optimal solution for Maximal Square?

Back to DSA Sheet