1277. Count Square Submatrices with All Ones LeetCode Solution
In this guide, you will get 1277. Count Square Submatrices with All Ones LeetCode Solution with the best time and space complexity. The solution to Count Square Submatrices with All Ones problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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: 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.
1277. Count Square Submatrices with All Ones LeetCode Solution in C++
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
for (int i = 0; i < matrix.size(); ++i)
for (int j = 0; j < matrix[0].size(); ++j)
if (matrix[i][j] == 1 && i > 0 && j > 0)
matrix[i][j] +=
min({matrix[i - 1][j - 1], matrix[i - 1][j], matrix[i][j - 1]});
return accumulate(matrix.begin(), matrix.end(), 0,
[](int subtotal, const vector<int>& row) {
return subtotal + accumulate(row.begin(), row.end(), 0);
});
}
}; /* code provided by PROGIEZ */
1277. Count Square Submatrices with All Ones LeetCode Solution in Java
class Solution {
public int countSquares(int[][] matrix) {
for (int i = 0; i < matrix.length; ++i)
for (int j = 0; j < matrix[0].length; ++j)
if (matrix[i][j] == 1 && i > 0 && j > 0)
matrix[i][j] +=
Math.min(matrix[i - 1][j - 1], Math.min(matrix[i - 1][j], matrix[i][j - 1]));
return Arrays.stream(matrix).flatMapToInt(Arrays::stream).sum();
}
} // code provided by PROGIEZ
1277. Count Square Submatrices with All Ones LeetCode Solution in Python
class Solution:
def countSquares(self, matrix: list[list[int]]) -> int:
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 1 and i > 0 and j > 0:
matrix[i][j] += min(matrix[i - 1][j - 1],
matrix[i - 1][j], matrix[i][j - 1])
return sum(map(sum, matrix)) # code by PROGIEZ
