Maximal Square Solution for Google
Company: Google · Difficulty: Medium · Topics: Dynamic Programming, Matrix
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.
Key Understanding:
- We need to find the largest square (not rectangle) of 1's
- A square has equal width and height
- The area is the side length squared
- We need to handle edge cases like single 1's and all 0's
- The matrix can be of any size m x n
Examples
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
Explanation:
- The largest square has side length 2
- Area = 2² = 4
- Visual representation:
```
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1 ← Largest square (2x2)
1 0 0 1 0
```
Example 2:
Input: matrix = [["0","1"],["1","0"]]
Output: 1
Explanation:
- No square larger than 1x1 exists
- Area = 1² = 1
- Visual representation:
```
0 1
1 0 ← Only 1x1 squares possible
```
Example 3:
Input: matrix = [["1","1","1"],["1","1","1"],["1","1","1"]]
Output: 9
Explanation:
- The entire matrix is a 3x3 square of 1's
- Area = 3² = 9
- Visual representation:
```
1 1 1
1 1 1 ← 3x3 square
1 1 1
```
Example 4:
Input: matrix = [["0"]]
Output: 0
Explanation:
- No square of 1's exists
- Area = 0
Example 5:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"],["1","1","1","1","1"]]
Output: 9
Explanation:
- The largest square has side length 3
- Area = 3² = 9
- Visual representation:
```
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
1 1 1 1 1 ← 3x3 square
```
Intuition
The key insight is that we can use dynamic programming to build the solution incrementally. For each cell, if it's a 1, the size of the largest square ending at that cell depends on the minimum of the three adjacent cells (top, left, and top-left).
Core Concept:
- If a cell is 0, it cannot be part of any square
- If a cell is 1, the largest square ending at that cell is 1 + min(top, left, top-left)
- This works because a square requires all four corners to be 1's
Why Dynamic Programming Works:
- We build the solution bottom-up
- Each cell's value depends on previously computed values
- We can reuse computed results to avoid recalculation
- This gives us optimal substructure
Mathematical Insight:
- For a square of size k ending at (i,j), we need:
- (i,j) = 1
- (i-1,j) ≥ k-1
- (i,j-1) ≥ k-1
- (i-1,j-1) ≥ k-1
- Therefore, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
Approach
Approach 1: Dynamic Programming (Optimal)
Algorithm:
1. Create a DP table of same size as input matrix
2. Initialize first row and column with matrix values
3. For each cell (i,j) where i > 0 and j > 0:
- 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
4. Track maximum value in DP table
5. Return maximum value squared
Why This Works:
- We build squares incrementally
- Each cell's value represents the side length of largest square ending there
- We take minimum of three adjacent cells to ensure square property
- This guarantees we find the largest possible square
Complexity Analysis:
- Time: O(m*n) - We visit each cell once
- Space: O(m*n) - We need a DP table
Approach 2: Dynamic Programming with Space Optimization
Algorithm:
1. Use a single row to store DP values
2. Keep track of previous row's values
3. Update current row using previous row and current matrix values
4. Track maximum value
5. Return maximum value squared
Why This Works:
- We only need the previous row to compute current row
- This reduces space complexity significantly
- Still maintains the same logic as full DP
Complexity Analysis:
- Time: O(m*n) - We visit each cell once
- Space: O(n) - We only store one row
Approach 3: Brute Force
Algorithm:
1. For each cell, try all possible square sizes
2. Check if the square contains only 1's
3. Track the largest valid square found
4. Return the area of largest square
Why This Works:
- We try all possible squares
- This guarantees we find the optimal solution
- Simple to understand and implement
Complexity Analysis:
- Time: O(m*n*min(m,n)²) - For each cell, try all square sizes
- Space: O(1) - Constant extra space
Dry Run
Let's trace through Example 1: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Dynamic Programming Approach:
Step 1: Initialize DP table
```
Matrix: DP Table:
1 0 1 0 0 1 0 1 0 0
1 0 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 1 0 0 1 0
```
Step 2: Fill DP table (starting from row 1, col 1)
- (1,1): matrix[1][1] = '0' → dp[1][1] = 0
- (1,2): matrix[1][2] = '1' → dp[1][2] = 1 + min(0,1,0) = 1
- (1,3): matrix[1][3] = '1' → dp[1][3] = 1 + min(0,1,1) = 1
- (1,4): matrix[1][4] = '1' → dp[1][4] = 1 + min(0,1,1) = 1
- (2,0): matrix[2][0] = '1' → dp[2][0] = 1 + min(1,0,0) = 1
- (2,1): matrix[2][1] = '1' → dp[2][1] = 1 + min(1,1,0) = 1
- (2,2): matrix[2][2] = '1' → dp[2][2] = 1 + min(1,1,1) = 2
- (2,3): matrix[2][3] = '1' → dp[2][3] = 1 + min(1,1,2) = 2
- (2,4): matrix[2][4] = '1' → dp[2][4] = 1 + min(1,1,2) = 2
Step 3: Final DP table
```
DP Table:
1 0 1 0 0
1 0 1 1 1
1 1 2 2 2
1 0 0 1 0
```
Step 4: Find maximum value
- Maximum value = 2
- Area = 2² = 4
Space Optimized Approach:
Step 1: Initialize
- prevRow = [1,0,1,0,0]
- maxSide = 1
Step 2: Process each row
- Row 1: currRow = [1,0,1,1,1] → maxSide = 1
- Row 2: currRow = [1,1,2,2,2] → maxSide = 2
- Row 3: currRow = [1,0,0,1,0] → maxSide = 2
Step 3: Return maxSide² = 4
Key Insights
1. Optimal Substructure: Each cell depends on three adjacent cells
2. Square Property: A square requires all four corners to be 1's
3. Minimum Rule: Take minimum of three adjacent cells to ensure square
4. Space Optimization: Only need previous row for current computation
5. Edge Cases: Handle first row and column separately
Edge Cases
1. Single Element: Matrix with one element
2. All Zeros: Matrix with no 1's
3. All Ones: Matrix with all 1's
4. Single Row/Column: Matrix with only one row or column
5. Large Matrix: Handle large matrices efficiently
6. Mixed Values: Matrix with both 0's and 1's
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution 1: Dynamic Programming (Optimal)
Time Complexity: O(m*n) - We visit each cell once
Space Complexity: O(m*n) - We need a DP table
Advantages:
- Most intuitive approach
- Easy to understand and implement
- Handles all edge cases
- Optimal time complexity
Disadvantages:
- Uses extra space for DP table
- Not space optimized
Solution 2: Dynamic Programming with Space Optimization
Time Complexity: O(m*n) - We visit each cell once
Space Complexity: O(n) - We only store one row
Advantages:
- Space efficient
- Same time complexity as full DP
- Good for large matrices
Disadvantages:
- Slightly more complex implementation
- Harder to understand
Solution 3: Brute Force
Time Complexity: O(m*n*min(m,n)²) - For each cell, try all square sizes
Space Complexity: O(1) - Constant extra space
Advantages:
- Simple and straightforward
- Easy to implement
- No extra space needed
Disadvantages:
- Less efficient
- Higher time complexity
- Not suitable for large matrices