Count Square Submatrices with All Ones — Problem & Solution
Count Square Submatrices with All Ones solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Square Submatrices with All Ones is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google and Uber interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Matrix
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an m × n matrix of ones and zeros, return how many square submatrices consist entirely of ones. Squares of every size count, including 1 × 1.
Example 1
Input: matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]
Output: 15
Explanation: There are 10 squares of side 1, 4 of side 2 and 1 of side 3.
Example 2
Input: matrix = [[1,0,1],[1,1,0],[1,1,0]]
Output: 7
Example 3
Input: matrix = [[1]]
Output: 1
Constraints
1 <= matrix.length, matrix[i].length <= 8matrix[i][j] is 0 or 1.
Hints for Count Square Submatrices with All Ones
Hint 1
Reuse the maximal-square recurrence:
dp[r][c]is the side of the largest all-ones square ending at(r, c).Hint 2
A cell with
dp[r][c] = kis the bottom-right corner of exactlyksquares — one of each side from 1 to k.Hint 3
So the answer is the sum of the whole dp table, not its maximum.
How to solve Count Square Submatrices with All Ones
Reuse the maximal-square recurrence: a cell with dp = k is the bottom-right corner of exactly k all-ones squares (sides 1 … k), so the answer is the sum of the table.
Approach
- Compute
dp[r][c] = 1 + min(up, left, up-left)for each 1-cell (1 on the border). - Accumulate every
dp[r][c].
Why it works
Every all-ones square has a unique bottom-right corner, and at that corner squares of every side up to the maximum exist, so summing the maximal sides counts every square exactly once.
Complexity
- Time —
O(m · n) - Space —
O(m · n)
Pitfalls
- Take the sum, not the maximum, of the table.
Reference solution
Python
def countSquares(matrix) -> int:
m, n = len(matrix), len(matrix[0])
dp = [[0] * n for _ in range(m)]
total = 0
for r in range(m):
for c in range(n):
if matrix[r][c] == 1:
if r == 0 or c == 0:
dp[r][c] = 1
else:
dp[r][c] = min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1]) + 1
total += dp[r][c]
return totalJava
public static int countSquares(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] dp = new int[m][n];
int total = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (matrix[r][c] == 1) {
if (r == 0 || c == 0) dp[r][c] = 1;
else dp[r][c] = Math.min(dp[r - 1][c], Math.min(dp[r][c - 1], dp[r - 1][c - 1])) + 1;
total += dp[r][c];
}
}
}
return total;
}C++
int countSquares(vector<vector<int>>& matrix) {
int m = (int) matrix.size(), n = (int) matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
int total = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (matrix[r][c] == 1) {
if (r == 0 || c == 0) dp[r][c] = 1;
else dp[r][c] = min(dp[r - 1][c], min(dp[r][c - 1], dp[r - 1][c - 1])) + 1;
total += dp[r][c];
}
}
}
return total;
}JavaScript
var countSquares = function(matrix) {
const m = matrix.length, n = matrix[0].length;
const dp = [];
for (let r = 0; r < m; r++) dp.push(new Array(n).fill(0));
let total = 0;
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (matrix[r][c] === 1) {
if (r === 0 || c === 0) dp[r][c] = 1;
else dp[r][c] = Math.min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1]) + 1;
total += dp[r][c];
}
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming