613. Count Square Submatrices with All Ones
You receive a binary matrix matrix with m rows and n columns; every cell is a 0 or a 1. Return how many square submatrices are made up entirely of ones.
Every axis-aligned square counts, at every size: each lone 1 is a 1×1 square, each 2×2 block of ones adds one more, and so on. Squares are counted at every position they occur, so overlapping squares each count separately.
Example 1:
Input: matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]
Output: 15
Explanation: There are ten 1×1 squares (one per 1-cell), four 2×2 squares, and one 3×3 square in the right block: 10 + 4 + 1 = 15.
Example 2:
Input: matrix = [[1,0,1],[1,1,0],[1,1,0]]
Output: 7
Explanation: Six 1-cells give six 1×1 squares, and the bottom-left 2×2 block of ones adds one more: 6 + 1 = 7.
Constraints:
- 1 ≤ m, n ≤ 300
- matrix[i][j] is 0 or 1
Hints:
Counting every square directly means checking every top-left corner at every size — that's a lot of repeated work over the same cells.
Define dp[i][j] = the side length of the largest all-ones square whose bottom-right corner sits at (i, j). If that value is 3, then squares of sides 1, 2, and 3 all end there — so dp[i][j] is also the NUMBER of squares ending at (i, j).
When matrix[i][j] = 1, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]). The answer is the sum of all dp values.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]
Expected output: 15