Count Square Submatrices with All Ones
Medium · 2-D Dynamic Programming · Array · Dynamic Programming · Matrix
Problem
You are given an m × n matrix of 0s and 1s. Count every square submatrix whose cells are all 1.
Squares of every size count, from 1 × 1 upward, and squares that overlap are counted separately.
Examples
Input: matrix = [[1,1,0],[1,1,1],[0,1,1]] Output: 9
Seven 1 × 1 squares and two 2 × 2 squares.
Input: matrix = [[1,1,1],[1,1,1],[1,1,1]] Output: 14
Nine 1 × 1, four 2 × 2 and one 3 × 3 square.
Input: matrix = [[0,0]] Output: 0
There are no ones at all.
Constraints
- 1 <= m, n <= 300
- matrix[i][j] is 0 or 1
Approaches
- Baseline: grow a square from every corner — time O(m · n · k²), space O(1)
Follow-up
The largest value in the same table is the side of the largest all-ones square (the maximal square problem). Since a row only reads the row above, the table can shrink to one row, or the counts can be written into matrix itself: O(1) extra space. Rectangles of ones are harder: counting them needs a histogram of heights per row and a monotonic stack.
Related problems
Start free on Cariara · Coding problems · System design studio
