Tally of Solid Squares
Medium2-D Dynamic Programming
Problem
A pixel mask is stored as a binary grid mask. Count every square sub-grid (of any size, aligned with the grid) whose cells are all 1.
Squares of different sizes or positions are counted separately, even when they overlap.
Example 1
- Input:
- mask = [[1, 1, 0], [1, 1, 1], [0, 1, 1]]
- Output:
- 9
Seven 1 × 1 squares plus two 2 × 2 squares (top-left and bottom-right).
Example 2
- Input:
- mask = [[1, 1, 1], [1, 1, 1]]
- Output:
- 8
Six 1 × 1 squares and two 2 × 2 squares.
Constraints
- 1 ≤ mask.length, mask[0].length ≤ 300
- mask[r][c] is 0 or 1
Hint
Show the first hint
Group squares by their bottom-right corner.
Walkthrough
How to approach it
01Clarify before coding
- Do overlapping squares count separately? Yes, each (position, size) is one square.
- Do 1 × 1 squares count? Yes, every single 1-cell is a square.
- How large can the answer get? For a 300 × 300 all-1 grid it is the sum of k² up to 300, about 9 · 10^6: fits easily.
02Brute force
For every top-left corner and every size, check whether the square is all 1s.
Cost: O(m · n · min(m, n)³) naively, or O(m · n · min(m, n)) with a 2-D prefix sum; both are far above O(m · n).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.