Count Square Submatrices with All Ones|

Easy

Each cell counts the squares ending there

Problem

Count all square submatrices that contain only 1s.

In simple words

Each cell counts squares ending there (its neighbour-min + 1); sum them for the total.

The idea

For a cell containing 1, the largest square with that cell as its bottom-right corner is one plus the minimum of the three neighbouring values. That number is also how many squares end at that cell, so summing the table gives the answer.

The trick

dp[i][j] = 1 + min(up, left, diagonal) when the cell is 1.
The value doubles as the count of squares ending there — sum the whole table.
O(rows × cols).

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

←→stepspaceplay

1/2

Optimal

timeO(m*n)spaceO(n)

1dp[i][j]=matrix[i][j]==1 ? 1+min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) : 02sum all dp

Input

array: [0, 1, 1, 1]

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]
Output:: 15
Explanation:: All-1 squares of every size total 15.

Example 2

Input:: matrix = [[1,0,1],[1,1,0],[1,1,0]]
Output:: 7
Explanation:: 7 all-1 squares.

Example 3

Input:: matrix = [[1]]
Output:: 1
Explanation:: One 1 → one square.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.