• Leetcode POTDs

Problem 1277 Count Square Submatrices with All Ones

Problem Statement

Link - Problem 1277

Question

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 <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

Solution

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int row = matrix.size(), col = matrix[0].size();
        vector<vector<int>> dp(row + 1, vector<int>(col + 1, 0));
        int ans = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == 1) {
                    dp[i + 1][j + 1] = min({dp[i][j + 1], dp[i + 1][j], dp[i][j]}) + 1;
                    ans += dp[i + 1][j + 1];
                }
            }
        }
        return ans;
    }
};

Complexity Analysis

| Algorithm                               | Time Complexity | Space Complexity |
| --------------------------------------- | --------------- | ---------------- |
| Dynamic Programming for perfect squares | O(nm)           | O(nm)            |

Explanation

1. Intuition

• The problem can be solved by using dynamic programming to build up a table of the size of the largest square that can be formed at each position.
• The key insight is that the size of the largest square that can be formed at a position is determined by the minimum size of the largest squares that can be formed at the positions above, to the left, and diagonally above-left.
• This is because a square can only be formed if all of the positions that make up the square are 1.
• By using dynamic programming, we can efficiently build up the table of largest square sizes without having to recompute the same values multiple times.
• The final answer is the sum of the sizes of all the squares that can be formed at each position.
• This approach works because it takes into account the fact that a larger square can be formed by adding a row or column to a smaller square.
• The time complexity of this approach is O(mn), where m and n are the dimensions of the input matrix.

2. Implementation

• The solution starts by initializing a 2D array dp of size (row+1) x (col+1) to store the size of the largest square that can be formed at each position.
• The dp array is initialized with zeros, and the ans variable is initialized to zero to store the final answer.
• The solution then iterates over each position in the input matrix, and if the value at the current position is 1, it updates the value in the dp array using the formula dp[i + 1][j + 1] = min({dp[i][j + 1], dp[i + 1][j], dp[i][j]}) + 1.
• The ans variable is then updated by adding the value of dp[i + 1][j + 1] to it.
• The solution uses the min function to find the minimum value of the largest squares that can be formed at the positions above, to the left, and diagonally above-left.
• The + 1 in the formula is used to increment the size of the largest square that can be formed at the current position.
• Finally, the solution returns the value of ans, which is the sum of the sizes of all the squares that can be formed at each position.

Complexity Analysis

Time Complexity:

• The time complexity of the algorithm is O(n*m) where n is the number of rows and m is the number of columns in the input matrix. This is because we are iterating through each element in the matrix once.
• The dominant operations are the two nested for loops for (int i = 0; i < row; i++) and for (int j = 0; j < col; j++), each of which has a time complexity of O(n) and O(m) respectively.
• The Big O classification justifies the time complexity as O(nm) because the two loops are nested, causing the time complexity to multiply. This satisfies the property of Big O notation where constant factors are ignored, and we are left with O(nm).

Space Complexity:

• The memory usage in this algorithm is primarily due to the creation of a new vector dp with dimensions (row+1) x (col+1) to store the lengths of the sides of perfect squares ending at each position in the matrix.
• The space impact of the dp vector is significant, resulting in a space complexity of O(nm) where n and m are the dimensions of the input matrix. This is because the size of the dp vector is directly proportional to the size of the input matrix.
• Justification of space complexity is that we need to store the values for all possible subproblems in the dp vector, and the number of these subproblems is equal to the number of elements in the input matrix, hence the space complexity of O(nm).

Footnote

This question is rated as Medium difficulty.

Hints

Create an additive table that counts the sum of elements of submatrix with the superior corner at (0,0).

Loop over all subsquares in O(n^3) and check if the sum make the whole array to be ones, if it checks then add 1 to the answer.

Similar Questions: