1277. Count Square Submatrices with All Ones
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:
Explanation:
There are squares of side .
There are squares of side .
There is square of side .
Total number of squares .
Example 2:
Input:
matrix = [ [1,0,1], [1,1,0], [1,1,0] ]
Output:
Explanation:
There are squares of side .
There is square of side .
Total number of squares .
Constraints:
-
arr.length
-
arr[0].length
-
arr[i][j]
Solution
Brute Force
First, let's say that a square is located at a cell (i,j)
if its bottom right corner is located at that cell.
We can observe that if there is a length square with all ones located at (i,j)
, then there exists squares with all ones that have lengths . This is because if a square submatrix with length located there exists, then square submatrices with lengths must exist as well.
For each cell (i,j)
we'll find the length of the largest square submatrix that has all ones with its bottom right corner located at (i,j)
. Let's denote this value as . We can observe that the number of square submatrices with all ones and its bottom right corner located at (i,j)
is simply . To find , we can brute force through all possible lengths and check if a square submatrix with that respective length exists. Once we find for each cell (i,j)
, our final answer is the sum of all .
Full Solution
Our full solution will involve dynamic programming.
Let dp[i][j]
represent .
Since dynamic programming uses the answers to sub-problems to calculate answers to a larger problem, let's try to see how we can use other values from dp
to calculate dp[i][j]
for some cell (i,j)
.
Let's say that a square submatrix is located at a cell (i,j)
if its bottom right corner is located there.
First, let's assume dp[i][j] = k
for some positive integer . This means that the largest square submatrix with all ones located at (i,j)
has length . We can observe that this means there exists square submatrices with all ones at (i,j-1)
, (i-1,j)
, and (i-1,j-1)
that have length . In addition, the cell (i,j)
is also .
If we look at all the cells that are covered by the square submatrices at (i,j-1)
, (i-1,j)
, and (i-1,j-1)
with length and the cell at (i,j)
, we obtain a square with length located at (i,j)
.
Example
Here is a diagram with and the cell at (5,5)
to help visualize this observation.
From the observation mentioned above, we can deduce that dp[i-1][j], dp[i][j-1], dp[i-1][j-1]
.
For dp[i][j]
to be greater or equal to , then (i,j)
must be and dp[i-1][j], dp[i][j-1], dp[i-1][j-1]
all have to be greater or equal to .
This translates into dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1
if the cell (i,j)
is a . For most cases, this is how we can calculate dp[i][j]
.
If the cell is in the first row or column however (i.e. or ), then dp[i][j]
is the same value as the cell (i,j)
.
Obviously, if the cell (i,j)
is , then dp[i][j] = 0
.
Our final answer is just the sum of all values stored in dp
.
Time Complexity
We can calculate the value of a cell in dp
in and since there are cells, our time complexity is .
Time Complexity:
Space Complexity
We store cells in dp
so our space complexity is .
Space Complexity:
Bonus: We can use the space optimization mentioned in this article to optimize memory to . Since we only use rows and in dp
to calculate dp
values for row , we only need to maintain two rows of memory for dp
, which is .
C++ Solution
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size(); // dimensions for matrix
int ans = 0;
vector<vector<int>> dp(m, vector<int>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) { // cell is in first row or column
dp[i][j] = matrix[i][j];
} else if (matrix[i][j] == 1) {
dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
}
ans += dp[i][j];
}
}
return ans;
}
};
Java Solution
class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length; // dimensions for matrix
int[][] dp = new int[m][n];
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) { // cell is in first row or column
dp[i][j] = matrix[i][j];
} else if (matrix[i][j] == 1) {
dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
}
ans += dp[i][j];
}
}
return ans;
}
}
Python Solution
class Solution: def countSquares(self, matrix: List[List[int]]) -> int: m = len(matrix) n = len(matrix[0]) # dimensions for matrix dp = [[0] * n for a in range(m)] ans = 0 for i in range(m): for j in range(n): if i == 0 or j == 0: # cell is in first row or column dp[i][j] = matrix[i][j] elif matrix[i][j] == 1: dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 ans += dp[i][j] return ans
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorWhich of the following uses divide and conquer strategy?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!