Count Square Submatrices with All Ones solution and explanation
Google
9 more videos on this problem
DP 56. Count Square Submatrices with All Ones | DP on Rectangles 🔥take U forward · 15:59 · 170K views
Count Square Submatrices with All Ones - Leetcode 1277 - PythonNeetCodeIO · 22:01 · 18K views
Count Square Submatrices with All Ones | Recursion | Bottom Up | Leetcode 1277 | codestorywithMIKcodestorywithMIK · 42:01 · 17K views
LeetCode 1277. Count Square Submatrices with All Ones Explanation and Solutionhappygirlzt · 9:40 · 5K views
Count Square Submatrices with All Ones | Dynamic Programming | Leetcode 1277Techdose · 15:26 · 3K views
LeetCode 1277. Count Square Submatrices with All OnesHappy Coding · 15:16 · 605 views
Count Square Submatrices with All Ones Leetcode - Dynamic Programming 1277 PythonPersistent Programmer · 17:57 · 503 views
Leetcode 1277. Count Square Submatrices with All Ones | Dynamic Programming | Python SolutionStatLearn Tech · 18:24 · 301 views
LeetCode 1277 | Count Square Submatrices with All Ones | Python DP Solution ExplainedBugNoJutsu · 4:34 · 124 views
1277. Count Square Submatrices with All Ones - Dynamic Programming SolutionAlgorithmicIQ · 8:28 · 115 views
The problem
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] <= 1
Approach overview
Problem 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 1: Dynamic Programming Approach
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.
def countSquares(matrix):
if not matrix or not matrix[0]:
return 0
m, n = len(matrix), len(matrix[0])
dp = [[0] * n for _ in range(m)]
count = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
continue
if i == 0 or j == 0:
dp[i][j] = matrix[i][j]
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
count += dp[i][j]
return countpublic class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length;
if (m == 0) return 0;
int n = matrix[0].length;
int[][] dp = new int[m][n];
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) continue;
if (i == 0 || j == 0) {
dp[i][j] = matrix[i][j];
} else {
dp[i][j] = 1 + Math.min(dp[i-1][j],
Math.min(dp[i][j-1], dp[i-1][j-1]));
}
count += dp[i][j];
}
}
return count;
}
}#include <vector>
#include <algorithm>
using namespace std;
int countSquares(vector<vector<int>>& matrix) {
int m = matrix.size();
if (m == 0) return 0;
int n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
int count = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 0) continue;
if (i == 0 || j == 0) {
dp[i][j] = matrix[i][j];
} else {
dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
}
count += dp[i][j];
}
}
return count;
}var countSquares = function(matrix) {
let m = matrix.length;
if (m === 0) return 0;
let n = matrix[0].length;
let dp = Array.from(Array(m), () => Array(n).fill(0));
let count = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 0) continue;
if (i === 0 || j === 0) {
dp[i][j] = matrix[i][j];
} else {
dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
}
count += dp[i][j];
}
}
return count;
};#include <stdio.h>
#include <string.h>
int countSquares(int** matrix, int matrixSize, int* matrixColSize) {
if(matrixSize == 0 || *matrixColSize == 0) return 0;
int count = 0;
int dp[matrixSize][*matrixColSize];
memset(dp, 0, sizeof(dp));
for (int i = 0; i < matrixSize; i++) {
for (int j = 0; j < *matrixColSize; j++) {
if (matrix[i][j] == 0) continue;
if (i == 0 || j == 0) {
dp[i][j] = matrix[i][j];
} else {
dp[i][j] = 1 + (matrix[i][j] ?
fmin(fmin(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) : 0);
}
count += dp[i][j];
}
}
return count;
}public class Solution {
public int CountSquares(int[][] matrix) {
int m = matrix.Length;
if (m == 0) return 0;
int n = matrix[0].Length;
int[,] dp = new int[m, n];
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) continue;
if (i == 0 || j == 0) {
dp[i, j] = matrix[i][j];
} else {
dp[i, j] = 1 + Math.Min(dp[i-1, j], Math.Min(dp[i, j-1], dp[i-1, j-1]));
}
count += dp[i, j];
}
}
return count;
}
}The Python implementation uses a list comprehension to initialize the dp matrix and tracks the count of square submatrices with nested loops. It handles special initialization for the first row and column to allow accurate tabulation of local submatrix counts stemming from oneself and neighboring values, resulting in an efficient solution.
Time Complexity: O(m * n).
Space Complexity: O(m * n) due to the inclusion of the auxiliary matrix dp.
Approach 2: Dynamic Programming
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].
- When
matrix[i][j] = 0, we havef[i][j] = 0. - When
matrix[i][j] = 1, the value of statef[i][j]depends on the values of the three positions above, left, and top-left:- If
i = 0orj = 0, thenf[i][j] = 1. - Otherwise
f[i][j] = min(f[i-1][j-1], f[i-1][j], f[i][j-1]) + 1.
- If
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.
function countSquares(matrix: number[][]): number {
const m = matrix.length;
const n = matrix[0].length;
const f: number[][] = Array.from({ length: m }, () => Array(n).fill(0));
let ans = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 0) {
continue;
}
if (i === 0 || j === 0) {
f[i][j] = 1;
} else {
f[i][j] = Math.min(f[i - 1][j - 1], Math.min(f[i - 1][j], f[i][j - 1])) + 1;
}
ans += f[i][j];
}
}
return ans;
}func countSquares(matrix [][]int) int {
m, n, ans := len(matrix), len(matrix[0]), 0
f := make([][]int, m)
for i := range f {
f[i] = make([]int, n)
}
for i, row := range matrix {
for j, v := range row {
if v == 0 {
continue
}
if i == 0 || j == 0 {
f[i][j] = 1
} else {
f[i][j] = min(f[i-1][j-1], min(f[i-1][j], f[i][j-1])) + 1
}
ans += f[i][j]
}
}
return ans
}impl Solution {
pub fn count_squares(matrix: Vec<Vec<i32>>) -> i32 {
let m = matrix.len();
let n = matrix[0].len();
let mut f = vec![vec![0; n]; m];
let mut ans = 0;
for i in 0..m {
for j in 0..n {
if matrix[i][j] == 0 {
continue;
}
if i == 0 || j == 0 {
f[i][j] = 1;
} else {
f[i][j] = std::cmp::min(f[i - 1][j - 1], std::cmp::min(f[i - 1][j], f[i][j - 1])) + 1;
}
ans += f[i][j];
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(m * n). |
| Dynamic Programming | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Count Square Submatrices with All Ones easy or hard?
The problem is classified as Medium because it requires recognizing a dynamic programming pattern on a matrix. Once the DP transition rule is understood, the implementation is straightforward and runs in linear time over the grid.
Count Square Submatrices with All Ones Python/Java solution
Python, Java, C++, C#, and JavaScript implementations follow the same DP formula. Iterate through the matrix and update each cell based on its top, left, and top-left neighbors. The accumulated DP values give the total square count.
How to solve Count Square Submatrices with All Ones in O(n)?
Treat the matrix as a grid DP problem. For each cell containing 1, compute dp[i][j] = 1 + min(top, left, top-left). This value represents the largest square ending at that position. Accumulate all dp values to get the total number of squares, resulting in O(m * n) time.
What is the best approach for Count Square Submatrices with All Ones?
Dynamic Programming is the best approach. For each cell, compute the size of the largest square ending there using 1 + min(top, left, top-left). Summing all DP values counts every valid square. This runs in O(m * n) time and is the expected interview solution.
Is Count Square Submatrices with All Ones asked at Google/Amazon/Meta?
Matrix dynamic programming problems similar to this appear frequently in interviews at companies like Amazon, Google, and Meta. The pattern of building solutions from neighboring cells is common in grid DP questions such as maximal square and minimum path problems.
What data structure is used in Count Square Submatrices with All Ones?
The main structure is a 2D dynamic programming table built on top of the input matrix. Each entry stores the largest square size ending at that cell. The algorithm also relies on standard matrix traversal using nested loops.
What is the time complexity of Count Square Submatrices with All Ones?
The optimal Dynamic Programming solution runs in O(m * n) time where m and n are the matrix dimensions. Each cell is processed once and performs constant-time comparisons with its neighbors. Space complexity is O(m * n) with a DP table or O(1) if the matrix is updated in place.