717. Count All Squares
A tiling robot inspects a wall panel grid where each cell is 1 (intact tile) or 0 (broken tile). A clean square is a square block of any side length at least 1, with sides parallel to the panel edges, in which every cell is 1.
Return how many clean squares the panel contains. Squares of different sizes or different positions are counted separately, so a lone 1 is one square and a fully intact 2 x 2 block holds five squares (four small ones and the whole block).
Aim for time O(rows * cols) and extra space O(cols).
Example 1
- Input:
- grid = [[1,1,0,1],[1,1,1,1],[0,1,1,1]]
- Output:
- 13
- Explanation:
Ten single cells plus three clean 2 x 2 blocks make 13 clean squares.
Example 2
- Input:
- grid = [[1,1,1,1],[1,1,1,1]]
- Output:
- 11
- Explanation:
Eight 1 x 1 squares plus three 2 x 2 squares give 11.
Constraints
1 ≤ rows, cols ≤ 300
grid[r][c] is 0 or 1
The answer fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(rows * cols)
- Space
- O(cols)