Log inSign up
mediumGeeksforGeeksNot Started

Largest Square of 1s

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

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an m × n binary matrix filled with 0s and 1s, find the largest square containing only `1`s and return its area (or its side length, depending on specification — standard LeetCode returns area).

### Example 1 - Input: ``text 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 largest square of 1s has side length 2, so area = 2 * 2 = 4`.

### Example 2 - Input: ``text matrix = [ ["0","1"], ["1","0"] ] ` - **Output**: 1`

Constraints:

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

What You'll Learn

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

  • Understand why the 3-neighbor minimum determines the maximum expandable square size.
  • Derive the bottom-right corner DP state definition.
  • Space-optimize the 2D grid to O(n) memory.

Pattern Recognition Trigger

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

Signals to Look For:

  • Finding largest contiguous square of identical elements in a 2D matrix.
  • Min-of-3 neighbors pattern.

Algorithmic Decision Tree:

  • Square ending at (i, j) requires all 3 adjacent sub-squares (top, left, diagonal) to have size at least k.
  • Area is square of max side length.

Connected Patterns:

Maximal RectangleCount Square Submatrices with All OnesMinimum Path Sum

1. All Top-Left Corners Expansion

Intuition

For every cell (i, j) with 1, test expanding squares of size 1, 2, 3... until a 0 is encountered.

Algorithm

  1. For each cell (r, c) from 0 to m - 1 and 0 to n - 1:
  2. If matrix[r][c] == '1':
  3. Set side = 1
  4. While expanding to side + 1 is within bounds and all new cells in row and col are 1:
  5. side++
  6. maxSide = max(maxSide, side)
  7. Return maxSide * maxSide.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int maximalSquareBrute(vector<vector<char>>& matrix) {
8 if (matrix.empty() || matrix[0].empty()) return 0;
9 int m = matrix.size(), n = matrix[0].size();
10 int maxSide = 0;
11
12 for (int r = 0; r < m; r++) {
13 for (int c = 0; c < n; c++) {
14 if (matrix[r][c] == '1') {
15 int side = 1;
16 bool flag = true;
17 while (r + side < m && c + side < n && flag) {
18 for (int k = r; k <= r + side; k++) {
19 if (matrix[k][c + side] == '0') { flag = false; break; }
20 }
21 for (int k = c; k <= c + side; k++) {
22 if (matrix[r + side][k] == '0') { flag = false; break; }
23 }
24 if (flag) side++;
25 }
26 maxSide = max(maxSide, side);
27 }
28 }
29 }
30 return maxSide * maxSide;
31}
32
33int main() {
34 vector<vector<char>> matrix = {
35 {'1','0','1','0','0'},
36 {'1','0','1','1','1'},
37 {'1','1','1','1','1'},
38 {'1','0','0','1','0'}
39 };
40 cout << "Max Area (Brute Force): " << maximalSquareBrute(matrix) << endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O((m * n) * min(m, n)^2)
  • Space complexity: O(1)

2. 2D Dynamic Programming Tabulation

Intuition

Build matrix dp[m + 1][n + 1] where dp[i][j] is side length of square ending at (i-1, j-1).

Algorithm

  1. Create dp of size (m + 1) x (n + 1) filled with 0.
  2. Initialize maxSide = 0.
  3. For i = 1 to m:
  4. For j = 1 to n:
  5. If matrix[i - 1][j - 1] == '1':
  6. dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]})
  7. maxSide = max(maxSide, dp[i][j])
  8. Return maxSide * maxSide.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int maximalSquare2D(vector<vector<char>>& matrix) {
8 if (matrix.empty() || matrix[0].empty()) return 0;
9 int m = matrix.size(), n = matrix[0].size();
10 vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
11 int maxSide = 0;
12
13 for (int i = 1; i <= m; i++) {
14 for (int j = 1; j <= n; j++) {
15 if (matrix[i - 1][j - 1] == '1') {
16 dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
17 maxSide = max(maxSide, dp[i][j]);
18 }
19 }
20 }
21 return maxSide * maxSide;
22}
23
24int main() {
25 vector<vector<char>> matrix = {
26 {'1','0','1','0','0'},
27 {'1','0','1','1','1'},
28 {'1','1','1','1','1'},
29 {'1','0','0','1','0'}
30 };
31 cout << "Max Area (2D DP): " << maximalSquare2D(matrix) << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

3. 1D Array Space-Optimized DP

Intuition

Maintain a single 1D array dp of size n + 1 with a scalar prev preserving the top-left diagonal value.

Algorithm

  1. Initialize array dp of size n + 1 filled with 0.
  2. maxSide = 0.
  3. For i = 1 to m:
  4. prev = 0
  5. For j = 1 to n:
  6. temp = dp[j]
  7. If matrix[i - 1][j - 1] == '1':
  8. dp[j] = 1 + min({dp[j], dp[j - 1], prev})
  9. maxSide = max(maxSide, dp[j])
  10. Else: dp[j] = 0
  11. prev = temp
  12. Return maxSide * maxSide.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int maximalSquareOptimal(vector<vector<char>>& matrix) {
8 if (matrix.empty() || matrix[0].empty()) return 0;
9 int m = matrix.size(), n = matrix[0].size();
10 vector<int> dp(n + 1, 0);
11 int maxSide = 0;
12
13 for (int i = 1; i <= m; i++) {
14 int prev = 0;
15 for (int j = 1; j <= n; j++) {
16 int temp = dp[j];
17 if (matrix[i - 1][j - 1] == '1') {
18 dp[j] = 1 + min({dp[j], dp[j - 1], prev});
19 maxSide = max(maxSide, dp[j]);
20 } else {
21 dp[j] = 0;
22 }
23 prev = temp;
24 }
25 }
26 return maxSide * maxSide;
27}
28
29int main() {
30 vector<vector<char>> matrix = {
31 {'1','0','1','0','0'},
32 {'1','0','1','1','1'},
33 {'1','1','1','1','1'},
34 {'1','0','0','1','0'}
35 };
36 cout << "Max Area (Optimal 1D DP): " << maximalSquareOptimal(matrix) << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(n) auxiliary space

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.All Corners ExpansionO(m * n * min(m, n)^2)O(1)Expand squares from each 1 cell.Redundant cell verification
2.2D TabulationO(m * n)O(m * n)dp[i][j] = 1 + min(top, left, diag).Matrix allocation
3.1D Array Space OptimizedOptimalO(m * n)O(n)Single 1D array with prev diagonal scalar.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Returning the side length instead of the area (side * side).

Pitfall 2:

Setting dp[j] = 0 when encountering 0 is forgotten in the 1D space-optimized version (leaves stale data from previous row).

Crucial Edge Cases to Validate:

  • No 1s in matrix: Output is 0.
  • Single cell 1: Output is 1.
  • All 1s in an m x n matrix: Output is min(m, n)^2.

Interview Tips & Best Practices

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

  1. Always clarify if the question asks for side length or area. LeetCode 221 asks for area, whereas some online sheets ask for side length.

Quick Comprehension Check

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

1.Why must the recurrence take the MINIMUM of all three neighbors (top, left, and diagonal)?

Back to DSA Sheet