Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.
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. There are 4 squares of side 2. There is 1 square of side 3. Total number of squares = 10 + 4 + 1 = 15.
Example 2:
Input: matrix = [ [1,0,1], [1,1,0], [1,1,0] ] Output: 7 Explanation: There are 6 squares of side 1. There is 1 square of side 2. Total number of squares = 6 + 1 = 7.
Constraints:
1 <= arr.length <= 3001 <= arr[0].length <= 3000 <= arr[i][j] <= 1Problem Overview: You get a binary matrix. The task is to count how many square submatrices contain only 1s. Squares can be any size (1x1, 2x2, 3x3, etc.), as long as every cell inside the square is 1.
Approach 1: Brute Force Expansion (O(m * n * min(m,n)^2) time, O(1) space)
Iterate through every cell in the matrix and treat it as the top-left corner of a potential square. For each position containing 1, try expanding the square size step by step (1x1, 2x2, 3x3). Each expansion checks whether the newly added row and column still contain only 1s. If a zero appears, expansion stops. This method works but becomes expensive because every cell may attempt multiple square expansions.
Approach 2: Dynamic Programming (O(m * n) time, O(m * n) space)
The key insight: if a cell (i, j) contains 1, the largest square ending at that cell depends on its neighbors. Specifically, look at the top (i-1, j), left (i, j-1), and top-left (i-1, j-1) cells. The size of the square ending at (i, j) equals 1 + min(top, left, top-left). Store this value in a DP matrix where dp[i][j] represents the largest square whose bottom-right corner is at that cell. Summing all DP values gives the total number of valid squares. This approach leverages local subproblem reuse, a classic pattern in dynamic programming problems involving grids.
Approach 3: Space-Optimized Dynamic Programming (O(m * n) time, O(1) extra space)
You can reuse the original matrix to store DP values instead of maintaining a separate table. While iterating through the grid, update each matrix[i][j] using the same transition formula if the value is 1. The updated value now represents the largest square ending at that cell. Accumulate these values into the result. This version keeps the optimal time complexity while removing the extra DP array, which is useful when memory is tight. The technique appears frequently in grid-based matrix problems and optimization patterns within array processing.
Recommended for interviews: The Dynamic Programming solution is what interviewers expect. Brute force demonstrates understanding of the square-checking logic, but the DP transition 1 + min(top, left, top-left) shows you recognize overlapping subproblems and can reduce the complexity to O(m * n). Many matrix DP problems follow this exact pattern.
The dynamic programming approach involves creating a DP array where each element represents the size of the largest square submatrix ending at that element. We'll only consider elements that are 1s, as 0s can't be part of a square of 1s. For each element that is 1, it can be the bottom-right corner of a square submatrix; we consider the minimum of the sizes of squares ending directly above, to the left, and diagonally above and to the left of it, then add 1 to this value. Sum up all the values in the DP array to get the total count of square submatrices.
This C function calculates the number of square submatrices with all ones by using a dynamic programming matrix (dp). For each 1 in the input matrix, it calculates the maximum size of the square submatrix ending at that cell and increments the total count. Bound checks for the first row and column simplify initialization.
Time Complexity: O(m * n), where m and n are the number of rows and columns in the matrix, respectively.
Space Complexity: O(m * n), due to the auxiliary DP matrix used to store maximum square sizes at each point.
We define f[i][j] as the side length of the square submatrix with (i,j) as the bottom-right corner. Initially f[i][j] = 0, and the answer is sum_{i,j} f[i][j].
Consider how to perform state transition for f[i][j].
matrix[i][j] = 0, we have f[i][j] = 0.matrix[i][j] = 1, the value of state f[i][j] depends on the values of the three positions above, left, and top-left:i = 0 or j = 0, then f[i][j] = 1.f[i][j] = min(f[i-1][j-1], f[i-1][j], f[i][j-1]) + 1.The answer is sum_{i,j} f[i][j].
Time complexity O(m times n), space complexity O(m times n). Where m and n are the number of rows and columns of the matrix respectively.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(m * n), where m and n are the number of rows and columns in the matrix, respectively. |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Expansion | O(m * n * min(m,n)^2) | O(1) | Good for understanding the problem and validating logic on small matrices |
| Dynamic Programming | O(m * n) | O(m * n) | General optimal approach used in most interview solutions |
| Space-Optimized DP (In-place) | O(m * n) | O(1) | When memory is constrained or when modifying the input matrix is allowed |
DP 56. Count Square Submatrices with All Ones | DP on Rectangles 🔥 • take U forward • 158,922 views views
Watch 9 more video solutions →Practice Count Square Submatrices with All Ones with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor