Maximal Square solution and explanation
Google
9 more videos on this problem
Maximal Square - Top Down Memoization - Leetcode 221NeetCode · 19:50 · 107K views
Maximal square | Dynamic programming | Leetcode #221Techdose · 18:27 · 77K views
Maximal Square of Ones (LeetCode Day 27)Errichto Algorithms · 12:08 · 42K views
Maximal square | Dynamic programming | Leetcode #221 | Largest Square Submatrix of all 1'sCode with Alisha · 17:08 · 27K views
Maximal Square (LeetCode 221) | Full Solution using Memoization | Dynamic ProgrammingNikhil Lohia · 14:56 · 7K views
Maximal square leetcode | maximal square dynamic programming | leetcode | Amazon interview questionthecodingworld · 7:34 · 3K views
LeetCode 221. Maximal Square [ Algorithm + Code Explained]jayati tiwari · 13:03 · 3K views
Maximal Square - LeetCode 221 - Python [O(n) time and O(1) Space!]Deepti Talesra · 13:14 · 3K views
LeetCode Solution - 221 Maximal Square | Javascript, Dynamic ProgrammingThinkFWD · 35:59 · 2K views
[Java] Leetcode 221. Maximal Square [DP Min/Max Path to Target #3]Eric Programming · 14:44 · 1K views
The problem
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:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 4
Example 2:
Input: matrix = [["0","1"],["1","0"]] Output: 1
Example 3:
Input: matrix = [["0"]] Output: 0
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 300matrix[i][j]is'0'or'1'.
Approach overview
Problem Overview: You receive a binary matrix of '0' and '1'. The goal is to find the largest square containing only 1s and return its area. The challenge is detecting square expansion efficiently instead of checking every possible submatrix.
Approach 1: Dynamic Programming (O(m*n) time, O(m*n) space)
The key observation: a square ending at cell (i, j) can only grow if the three neighboring squares (i-1, j), (i, j-1), and (i-1, j-1) also support that expansion. Define dp[i][j] as the side length of the largest square whose bottom-right corner is at (i, j). If the matrix value is '1', compute dp[i][j] = 1 + min(top, left, diagonal). If it is '0', the value stays 0. While iterating through the matrix row by row, track the maximum side length seen so far and square it at the end to get the area. This approach transforms a brute-force square validation problem into a local recurrence using dynamic programming. Time complexity is O(m*n) because every cell is processed once. Space complexity is O(m*n) for the DP table.
Approach 2: Space Optimized DP (O(m*n) time, O(n) space)
The full DP table is not strictly required because each state depends only on the previous row and the current row. Instead of storing the entire matrix of DP states, maintain a single array representing the previous row plus a variable for the diagonal value. While iterating through columns, update the current cell using the same recurrence: 1 + min(top, left, diagonal). The trick is preserving the old value of dp[j] before overwriting it so it can act as the diagonal for the next computation. This reduces memory usage significantly while preserving the same logic. Time complexity remains O(m*n), but space drops to O(n), where n is the number of columns.
Both approaches rely on scanning the grid and updating state based on neighboring cells, a common pattern in matrix and array DP problems. The recurrence works because a larger square can only exist if all three adjacent smaller squares already exist.
Recommended for interviews: The standard dynamic programming approach is what interviewers typically expect. Explaining the recurrence dp[i][j] = 1 + min(top, left, diagonal) demonstrates understanding of 2D DP state transitions. After presenting that solution, mentioning the space optimization to O(n) shows deeper mastery and awareness of practical constraints.
Approach 1: Dynamic Programming Approach
In this approach, a dynamic programming (DP) table is used to store the size of the largest square whose bottom-right corner is at each cell. For each cell (i, j) with a value of '1', we check its top (i-1, j), left (i, j-1), and top-left (i-1, j-1) neighbors to determine the size of the largest square ending at (i, j). If any of these neighbors are '0', the square cannot extend to include (i, j). The formula is: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. The maximum value in the DP table will be the side length of the largest square, and the area is its square.
class Solution:
def maximalSquare(self, matrix):
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_side = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if matrix[i-1][j-1] == '1':
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
max_side = max(max_side, dp[i][j])
return max_side * max_sidepublic class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix.length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int[][] dp = new int[m+1][n+1];
int maxSide = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i-1][j-1] == '1') {
dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
}#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
int max_side = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (matrix[i-1][j-1] == '1') {
dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
max_side = max(max_side, dp[i][j]);
}
}
}
return max_side * max_side;
}
};var maximalSquare = function(matrix) {
if (matrix.length === 0) return 0;
const m = matrix.length;
const n = matrix[0].length;
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
let maxSide = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] === '1') {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
};#include <string.h>
int maximalSquare(char** matrix, int matrixSize, int* matrixColSize) {
if (matrixSize == 0 || *matrixColSize == 0) return 0;
int m = matrixSize, n = *matrixColSize;
int dp[m+1][n+1];
memset(dp, 0, sizeof(dp));
int max_side = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (matrix[i-1][j-1] == '1') {
dp[i][j] = fmin(fmin(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
if (dp[i][j] > max_side) {
max_side = dp[i][j];
}
}
}
}
return max_side * max_side;
}public class Solution {
public int MaximalSquare(char[][] matrix) {
if (matrix.Length == 0) return 0;
int m = matrix.Length, n = matrix[0].Length;
int[,] dp = new int[m + 1, n + 1];
int maxSide = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] == '1') {
dp[i, j] = Math.Min(Math.Min(dp[i - 1, j], dp[i, j - 1]), dp[i - 1, j - 1]) + 1;
maxSide = Math.Max(maxSide, dp[i, j]);
}
}
}
return maxSide * maxSide;
}
}The Python solution initializes a DP table with one extra row and column filled with zeros, to handle boundary conditions without additional checks. It iterates through the matrix, updating the DP table using the given formula and tracking the maximum square side found.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(m * n), due to the DP table.
Approach 2: Space Optimized DP Approach
This approach uses a similar DP strategy but optimizes space by utilizing a one-dimensional array instead of a full 2D DP table. The key idea is that while processing the matrix row by row, previous rows' information will be partially redundant. Hence, we can maintain only the current and previous row data in separate arrays or even use a single array with swap states.
class Solution:
def maximalSquare(self, matrix):
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
prev = [0] * (n + 1)
max_side = 0
for i in range(1, m + 1):
current = [0] * (n + 1)
for j in range(1, n + 1):
if matrix[i-1][j-1] == '1':
current[j] = min(prev[j], current[j-1], prev[j-1]) + 1
max_side = max(max_side, current[j])
prev = current
return max_side * max_sidepublic class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix.length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int[] prev = new int[n + 1];
int[] current = new int[n + 1];
int maxSide = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] == '1') {
current[j] = Math.min(Math.min(prev[j], current[j - 1]), prev[j - 1]) + 1;
maxSide = Math.max(maxSide, current[j]);
}
}
int[] tmp = prev;
prev = current;
current = tmp;
Arrays.fill(current, 0);
}
return maxSide * maxSide;
}
}#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int m = matrix.size(), n = matrix[0].size();
vector<int> prev(n + 1, 0);
vector<int> current(n + 1, 0);
int max_side = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (matrix[i-1][j-1] == '1') {
current[j] = min({prev[j], current[j-1], prev[j-1]}) + 1;
max_side = max(max_side, current[j]);
}
}
swap(prev, current);
fill(current.begin(), current.end(), 0);
}
return max_side * max_side;
}
};var maximalSquare = function(matrix) {
if (matrix.length === 0) return 0;
const m = matrix.length;
const n = matrix[0].length;
let prev = new Array(n + 1).fill(0);
let current = new Array(n + 1).fill(0);
let maxSide = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] === '1') {
current[j] = Math.min(prev[j], current[j - 1], prev[j - 1]) + 1;
maxSide = Math.max(maxSide, current[j]);
}
}
[prev, current] = [current, new Array(n + 1).fill(0)];
}
return maxSide * maxSide;
};#include <string.h>
#include <stdlib.h>
int maximalSquare(char** matrix, int matrixSize, int* matrixColSize) {
if (matrixSize == 0 || *matrixColSize == 0) return 0;
int m = matrixSize, n = *matrixColSize;
int* prev = (int*)calloc(n + 1, sizeof(int));
int* current = (int*)calloc(n + 1, sizeof(int));
int max_side = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (matrix[i-1][j-1] == '1') {
current[j] = fmin(fmin(prev[j], current[j-1]), prev[j-1]) + 1;
max_side = fmax(max_side, current[j]);
}
}
int* temp = prev;
prev = current;
current = temp;
memset(current, 0, (n + 1) * sizeof(int));
}
free(prev);
free(current);
return max_side * max_side;
}public class Solution {
public int MaximalSquare(char[][] matrix) {
if (matrix.Length == 0) return 0;
int m = matrix.Length, n = matrix[0].Length;
int[] prev = new int[n + 1];
int[] current = new int[n + 1];
int maxSide = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] == '1') {
current[j] = Math.Min(Math.Min(prev[j], current[j - 1]), prev[j - 1]) + 1;
maxSide = Math.Max(maxSide, current[j]);
}
}
Array.Copy(current, prev, n + 1);
Array.Clear(current, 0, n + 1);
}
return maxSide * maxSide;
}
}The space-optimized Python solution uses two arrays; one for the current row calculations and one for the previous row's data. After finishing each row, it swaps the references, reassigning the current as 'previous'. This approach reduces space use to O(n).
Time Complexity: O(m * n)
Space Complexity: O(n)
Approach 3: Dynamic Programming
We define dp[i + 1][j + 1] as the maximum square side length with the lower right corner at index (i, j). The answer is the maximum value among all dp[i + 1][j + 1].
The state transition equation is:
$
dp[i + 1][j + 1] =
\begin{cases}
0 & if matrix[i][j] = '0' \
min(dp[i][j], dp[i][j + 1], dp[i + 1][j]) + 1 & if matrix[i][j] = '1'
\end{cases}
The time complexity is O(mtimes n), and the space complexity is O(mtimes n). Where m and n$ are the number of rows and columns of the matrix, respectively.
func maximalSquare(matrix [][]byte) int {
m, n := len(matrix), len(matrix[0])
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1)
}
mx := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if matrix[i][j] == '1' {
dp[i+1][j+1] = min(min(dp[i][j+1], dp[i+1][j]), dp[i][j]) + 1
mx = max(mx, dp[i+1][j+1])
}
}
}
return mx * mx
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. |
| Space Optimized DP Approach | Time Complexity: O(m * n) |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (2D DP Table) | O(m*n) | O(m*n) | Best for clarity during interviews and when memory usage is not a concern |
| Space Optimized DP | O(m*n) | O(n) | Preferred when matrix is large and memory optimization matters |
Frequently asked questions
Is Maximal Square easy or hard?
Maximal Square is generally rated Medium difficulty. The challenge lies in recognizing the dynamic programming relationship between neighboring cells rather than checking all possible squares, which would be much slower.
How to solve Maximal Square in O(n) space?
Use a space-optimized dynamic programming approach that stores only one row of DP values. While scanning each row, keep track of the previous diagonal value before overwriting the current entry. This keeps the time complexity at O(m*n) but reduces memory usage to O(n).
What is the best approach for Maximal Square?
The optimal approach uses dynamic programming. For each cell in the matrix, compute the largest square ending at that position using the recurrence dp[i][j] = 1 + min(top, left, diagonal). This processes every cell once, giving O(m*n) time complexity and O(m*n) space, which can be optimized to O(n).
What data structure is used in Maximal Square?
The solution primarily uses a 2D or 1D dynamic programming array to store intermediate square sizes. The input itself is a matrix, and the DP array tracks the largest square ending at each position while iterating through the grid.
What is the time complexity of Maximal Square?
The standard dynamic programming solution runs in O(m*n) time, where m is the number of rows and n is the number of columns in the matrix. Each cell is processed exactly once and updated using constant-time comparisons with its neighbors.
Maximal Square Python or Java solution approach?
Both Python and Java implementations typically use the same DP recurrence: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) when the matrix cell is '1'. The algorithm runs in O(m*n) time and can be implemented with either a 2D DP table or a space-optimized 1D array.
Is Maximal Square asked at Google, Amazon, or Meta?
Maximal Square is a common matrix dynamic programming problem and has appeared in interviews at companies such as Amazon, Google, and Microsoft. It tests understanding of DP state transitions and optimization of 2D grid problems.