← OYO questions

Maximum size square sub-matrix with all 1s

Filed under OYO · Also reported at Amazon, EPAM, Expedia, Microsoft, Oracle

Free read 1 of 3

Confirm 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

  1. Confirm if the input matrix is guaranteed to be non-empty and if rectangular matrices are allowed.

Solution

O(rows * cols) time, O(rows * cols) space

Python
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.