Problem Statement
Given a binary matrix matrix, count the square submatrices whose cells are all 1.
A square may have any side length that fits inside the matrix. Count squares at different positions separately, even when they overlap. Return the total number of valid squares, including those of size 1 × 1.
Example 1
Input: matrix = [[1,1,1],[1,1,1],[0,1,1]]
Output: 11
Explanation: There are eight 1 × 1 squares, one for each cell containing 1. The three valid 2 × 2 squares have top-left corners at (0,0), (0,1), and (1,1), using zero-based indices. The only 3 × 3 square contains a 0, so it does not count. The answer is 8 + 3 = 11.
Example 2
Input: matrix = [[1,0,1,1],[1,1,1,1],[1,1,1,0]]
Output: 13
Explanation: Ten cells contain 1, giving ten 1 × 1 squares. Three 2 × 2 squares also contain only ones. Their top-left corners are (0,2), (1,0), and (1,1). Neither possible 3 × 3 square is valid, so the answer is 10 + 3 = 13.
Brute Force Approach
Start by checking every square that fits inside the matrix. Choosing a square requires fixing its top-left corner and its side length. Once those are fixed, the algorithm visits its cells and checks whether any of them contains 0.
If every cell is 1, add one to the answer. If a 0 is found, stop checking that square and move to the next candidate. This counts every valid square exactly once because each square has one top-left corner and one side length.
Algorithm
Find the number of rows and columns in the matrix, and initialize the answer to zero.
Visit every cell and consider it as the top-left corner of a square.
For each starting position, determine the maximum possible side length that keeps the square within the matrix boundaries.
Try every side length from one up to the maximum possible size.
Examine every cell inside the selected square, moving row by row.
If any cell contains zero, mark the square as invalid and stop checking its remaining cells.
If every cell contains one, increase the answer by one.
Repeat this process for all possible starting positions and square sizes.
Return the total number of valid square submatrices.
Dry Run
Count Square Submatrices with All Ones - Brute Force
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Checks whether all cells inside the given square submatrix are 1 bool isAllOnes(vector<vector<int>>& matrix, int startRow, int startCol, int size) { // loop through the current square grid for (int i = startRow; i < startRow + size; i++) { for (int j = startCol; j < startCol + size; j++) { // if we hit a 0, it's not a valid square of all 1s if (matrix[i][j] == 0) return false; } } return true; } // Counts the total number of square submatrices filled entirely with 1s int countSquares(vector<vector<int>>& matrix) { int n = matrix.size(); int m = matrix[0].size(); int ans = 0; // check every possible cell to be the top-left corner for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // max square size we can form without going out of bounds int limit = min(n - i, m - j); // try all valid square sizes starting from this cell for (int size = 1; size <= limit; size++) { if (isAllOnes(matrix, i, j, size)) { ans++; } } } } return ans; }};// Driver codeint main() { vector<vector<int>> matrix = { {1, 1, 1}, {1, 1, 1}, {0, 1, 1} }; Solution obj; cout << obj.countSquares(matrix) << endl; return 0;}Complexity Analysis
Time Complexity: O(N × M × S³) where S = min(N, M). For each of the N × M cells, checking all valid square sizes up to S takes O(S³) time.
Space Complexity: O(1), as no extra space is used.
Better Approach
The brute force approach repeatedly visits the same cells while checking overlapping squares. A 2D prefix-sum table avoids this repeated work by allowing the sum of any square submatrix to be calculated in constant time. The prefix-sum table contains an extra row at the top and an extra column on the left, both filled with zeros. Each remaining entry stores the sum of all matrix elements from the top-left corner up to the corresponding position.
To calculate the sum of a square, first take the sum of the larger rectangle ending at its bottom-right corner. Then subtract the regions above and to the left of the square. Since their shared top-left region gets subtracted twice, add it back once to obtain the correct sum. Because the matrix contains only zeros and ones, a square is filled entirely with ones when its sum equals its area. For example, a square with side length three must have a sum of nine.
This approach still checks every possible square, but the prefix-sum table makes each square-sum calculation take constant time.
Algorithm
Create a
(N + 1) × (M + 1)prefix-sum table filled with zeros.Build the table from top to bottom and left to right. Add the current matrix value, the sum above, and the sum to the left, then subtract the shared upper-left sum.
Set the answer to
0and visit every cell as a possible top-left corner.Try each side length that keeps the selected square inside the matrix.
Find its sum using the four corresponding entries in the prefix-sum table.
Add
1to the answer if that sum equals the side length squared.Return the answer after checking all candidates.
Dry Run
Count Square Submatrices with All Ones - Better
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Calculates the sum of elements in the given square submatrix int squareSum(vector<vector<int>>& prefix, int i, int j, int size) { int bottom = i + size; int right = j + size; // cut out the top and left rectangles, then add back the top-left overlap return prefix[bottom][right] - prefix[i][right] - prefix[bottom][j] + prefix[i][j]; } // Counts the total number of square submatrices filled entirely with 1s int countSquares(vector<vector<int>>& matrix) { int n = matrix.size(); int m = matrix[0].size(); // pad with an extra row and column of zeros so we don't need boundary checks vector<vector<int>> prefix(n + 1, vector<int>(m + 1, 0)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { // standard 2D prefix sum formula: current + top + left - top-left diagonal prefix[i][j] = matrix[i - 1][j - 1] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1]; } } int ans = 0; // check every possible cell to be the top-left corner for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // max square size we can make from here int limit = min(n - i, m - j); for (int size = 1; size <= limit; size++) { // since it's a binary matrix, if the sum equals the area, all cells must be 1 if (squareSum(prefix, i, j, size) == size * size) { ans++; } } } } return ans; }};// Driver codeint main() { vector<vector<int>> matrix = { {1, 1, 1}, {1, 1, 1}, {0, 1, 1} }; Solution sol; cout << sol.countSquares(matrix) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(N × M × S) where S = min(N, M). Building the prefix-sum table takes O(N × M) time, and checking all valid square sizes for each of the N × M cells takes O(N × M × S).
Space Complexity: O(N × M) to store the prefix-sum table.
Optimal Approach
Instead of checking squares one at a time, count how many valid squares end at each cell. A DP table stores the side length of the largest square containing only ones that ends at each position. If the current cell contains zero, no valid square can end there, so its DP value is zero. If the cell contains one and lies in the first row or first column, its DP value is one because there is not enough space above or to the left to form a larger square.
For any other cell containing one, examine the DP values directly above, directly to the left, and diagonally above-left. All three neighboring regions must support a larger square. Therefore, take the smallest of these three values and add one to determine the largest square ending at the current cell. Choosing a larger value could include cells that are not part of an all-ones square. If a DP value is two, both a square of side length one and a square of side length two end at that cell. Similarly, a DP value of three represents three valid squares of different sizes. Therefore, each DP value tells us how many valid squares end at that position.
By adding all DP values to the answer, every valid square is counted exactly once because each square has a unique bottom-right corner.
Algorithm
Create a DP table of size
N × M, initially filled with zeros. Initialize the answer to zero.Traverse the matrix row by row, from top to bottom and left to right, so the required neighboring DP values are already calculated.
If the current cell contains zero, keep its DP value as zero because no valid square can end there.
If the current cell contains one and lies in the first row or first column, set its DP value to one.
For any other cell containing one, find the smallest DP value among the top, left, and top-left diagonal neighbors. Add one to this minimum and store the result as the current DP value.
Add the current DP value to the answer because it represents the number of valid squares ending at that cell.
After processing every cell, return the answer.
Dry Run
Count Square Submatrices with All Ones - Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Counts the total number of square submatrices filled entirely with 1s int countSquares(vector<vector<int>>& matrix) { int n = matrix.size(); int m = matrix[0].size(); // dp stores the max square size ending at each cell vector<vector<int>> dp(n, vector<int>(m, 0)); int ans = 0; // process top to bottom, left to right for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (matrix[i][j] == 0) { dp[i][j] = 0; } else if (i == 0 || j == 0) { // first row or column can only form 1x1 squares dp[i][j] = 1; } else { // take the min of top, left, and diagonal, then add 1 dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}); } // add the size to our total count ans += dp[i][j]; } } return ans; }};// Driver codeint main() { vector<vector<int>> matrix = { {1, 1, 1}, {1, 1, 1}, {0, 1, 1} }; Solution sol; cout << sol.countSquares(matrix) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(N × M) where N and M are the number of rows and columns. Each cell is processed exactly once in constant time.
Space Complexity: O(N × M) to store the DP table.
Interview follow-up Questions
When we cut out the top and left rectangles to get our square's total, we accidentally remove their shared corner twice. Adding it back once fixes the math so we don't undercount.
Be the first to add a comment.