Count Square Submatrices with All Ones
Count Square Submatrices with All Ones is a medium dynamic programming problem solved with the squares pattern.
The best approach, optimal (same dp as maximal square, then sum), runs in O(m · n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force up.
Problem
Count all square submatrices consisting entirely of 1s, of every size.
Examples
Example 1
- Input
matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]- Output
15- Why
- 10 squares of side 1, 4 of side 2, 1 of side 3.
Example 2
- Input
matrix = [[1,0,1],[1,1,0],[1,1,0]]- Output
7
Constraints
1 <= m, n <= 300; values 0 or 1.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force | O(m · n · min(m, n)²) | O(1) |
| Optimal (same DP as Maximal Square, then sum) | O(m · n) | O(1) |
1Brute force
O(m · n · min(m, n)²)O(1)For every top-left corner and every size, check whether the square is all 1s.
- Grow each square layer by layer while it stays all 1s; count each size.
class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length, n = matrix[0].length, count = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
int size = 0;
grow:
while (i + size < m && j + size < n) {
for (int k = 0; k <= size; k++)
if (matrix[i + size][j + k] != 1 || matrix[i + k][j + size] != 1) break grow;
size++;
count++;
}
}
return count;
}
}class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
m, n, count = len(matrix), len(matrix[0]), 0
for i in range(m):
for j in range(n):
size = 0
while i + size < m and j + size < n:
if any(matrix[i + size][j + k] != 1 or matrix[i + k][j + size] != 1 for k in range(size + 1)):
break
size += 1
count += 1
return countclass Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size(), count = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
int size = 0;
while (i + size < m && j + size < n) {
bool ok = true;
for (int k = 0; k <= size; k++)
if (matrix[i + size][j + k] != 1 || matrix[i + k][j + size] != 1) { ok = false; break; }
if (!ok) break;
size++;
count++;
}
}
return count;
}
};function countSquares(matrix) {
const m = matrix.length, n = matrix[0].length;
let count = 0;
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++) {
let size = 0;
grow:
while (i + size < m && j + size < n) {
for (let k = 0; k <= size; k++)
if (matrix[i + size][j + k] !== 1 || matrix[i + k][j + size] !== 1) break grow;
size++;
count++;
}
}
return count;
}2Optimal (same DP as Maximal Square, then sum)
O(m · n)O(1)Updates the input in place.dp[i][j] = 1 + min(top, left, top-left) for each 1. Each dp value counts the squares whose bottom-right corner is that cell, so the answer is the sum of the table. It can be computed in place.
- For i, j >= 1 with matrix[i][j] == 1: matrix[i][j] = 1 + min(three neighbours).
- Sum every cell.
class Solution {
public int countSquares(int[][] matrix) {
int total = 0;
for (int i = 0; i < matrix.length; i++)
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 1 && i > 0 && j > 0)
matrix[i][j] = 1 + Math.min(matrix[i - 1][j - 1], Math.min(matrix[i - 1][j], matrix[i][j - 1]));
total += matrix[i][j];
}
return total;
}
}class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
total = 0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 1 and i > 0 and j > 0:
matrix[i][j] = 1 + min(matrix[i - 1][j - 1], matrix[i - 1][j], matrix[i][j - 1])
total += matrix[i][j]
return totalclass Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int total = 0;
for (int i = 0; i < (int)matrix.size(); i++)
for (int j = 0; j < (int)matrix[0].size(); j++) {
if (matrix[i][j] == 1 && i > 0 && j > 0)
matrix[i][j] = 1 + min(matrix[i - 1][j - 1], min(matrix[i - 1][j], matrix[i][j - 1]));
total += matrix[i][j];
}
return total;
}
};function countSquares(matrix) {
let total = 0;
for (let i = 0; i < matrix.length; i++)
for (let j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] === 1 && i > 0 && j > 0)
matrix[i][j] = 1 + Math.min(matrix[i - 1][j - 1], Math.min(matrix[i - 1][j], matrix[i][j - 1]));
total += matrix[i][j];
}
return total;
}Edge cases to test
- All zeros
Hints
Hint 1
If the largest square ending at (i, j) has side s, then exactly s squares end there (sides 1..s). Sum the DP table.
FAQ
What is the best time complexity for Count Square Submatrices with All Ones?
Optimal (same DP as Maximal Square, then sum) runs in O(m · n) time and O(1) extra space.
Which pattern does Count Square Submatrices with All Ones use?
It is a dynamic programming problem that uses the squares pattern. Other problems with the same pattern: Maximal Square, Largest 1-Bordered Square.
Is there a brute force solution for Count Square Submatrices with All Ones?
Yes. Brute force takes O(m · n · min(m, n)²) time and O(1) space. For every top-left corner and every size, check whether the square is all 1s.
Which edge cases should I test for Count Square Submatrices with All Ones?
All zeros.