Watch 10 video solutions for Count Square Submatrices with All Ones, a medium level problem involving Array, Dynamic Programming, Matrix. This walkthrough by take U forward has 158,922 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |