Maximum size square sub-matrix with all 1s
Filed under OYO · Also reported at Amazon, EPAM, Expedia, Microsoft, Oracle
Free read 1 of 3Confirm if the input matrix is guaranteed to be non-empty and if rectangular matrices are allowed.
The question
Given a 2D binary matrix of 0s and 1s, find the side length of the largest square sub-matrix containing only 1s.
Constraints
- Matrix dimensions up to 1000x1000
- Time complexity should be O(rows * cols)
- Space complexity should be O(rows * cols) or O(cols)
Examples
- Input
- [[1,0,1],[1,1,1],[1,1,1]]
- Output
- 2
- Why
- The largest square of 1s is a 2x2 square found in the bottom-right.
Approach
Confirm if the input matrix is guaranteed to be non-empty and if rectangular matrices are allowed.
Define dp[i][j] as the side length of the largest square ending at cell (i, j).
If matrix[i][j] is 1, dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. Otherwise, 0.
Handle the first row and first column separately as they cannot form squares larger than 1.
Solution
O(rows * cols) time, O(rows * cols) space
def maximalSquare(matrix):
if not matrix: return 0
rows, cols = len(matrix), len(matrix[0])
dp = [[0]*(cols + 1) for _ in range(rows + 1)]
max_side = 0
for r in range(1, rows + 1):
for c in range(1, cols + 1):
if matrix[r-1][c-1] == 1:
dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1
max_side = max(max_side, dp[r][c])
return max_side * max_side
Tips
- What they are testing: Tests boundary conditions like an empty matrix, a matrix with all 0s, and a matrix with all 1s.
- Common mistake: Attempting to solve using brute force (checking every square) which leads to O(N^4) or O(N^3) complexity.
Related OYO questions
Collected from public candidate posts and coding forums. Updated Nov 2026.