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:

1matrix =
2[
3  [0,1,1,1],
4  [1,1,1,1],
5  [0,1,1,1]
6]

Output: 1515
Explanation:
There are 1010 squares of side 11.
There are 44 squares of side 22.
There is 11 square of side 33.
Total number of squares =10+4+1=15= 10 + 4 + 1 = 15.

Example 2:

Input:

1matrix =
2[
3  [1,0,1],
4  [1,1,0],
5  [1,1,0]
6]

Output: 77
Explanation:
There are 66 squares of side 11.
There is 11 square of side 22.
Total number of squares =6+1=7= 6 + 1 = 7.

Constraints:

  • 1≀1 \leq arr.length ≀300\leq 300
  • 1≀1 \leq arr[0].length ≀300\leq 300
  • 0≀0 \leq arr[i][j] ≀1\leq 1

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 xx square with all ones located at (i,j), then there exists squares with all ones that have lengths xβˆ’1,xβˆ’2…,3,2,1x-1,x-2 \dots, 3,2,1. This is because if a square submatrix with length xx located there exists, then square submatrices with lengths xβˆ’1,xβˆ’2…3,2,1x-1, x-2 \dots 3,2,1 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 xi,jx_{i,j}. We can observe that the number of square submatrices with all ones and its bottom right corner located at (i,j) is simply xi,jx_{i,j}. To find xi,jx_{i,j}, we can brute force through all possible lengths and check if a square submatrix with that respective length exists. Once we find xi,jx_{i,j} for each cell (i,j), our final answer is the sum of all xi,jx_{i,j}.

Full Solution

Our full solution will involve dynamic programming.

Let dp[i][j] represent xi,jx_{i,j}.

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 kk. This means that the largest square submatrix with all ones located at (i,j) has length kk. 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 kβˆ’1k-1. In addition, the cell (i,j) is also 11.

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 kβˆ’1k-1 and the cell at (i,j), we obtain a square with length kk located at (i,j).

Example

Here is a diagram with k=5k = 5 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] β‰₯kβˆ’1\geq k-1.

For dp[i][j] to be greater or equal to kk, then (i,j) must be 11 and dp[i-1][j], dp[i][j-1], dp[i-1][j-1] all have to be greater or equal to kβˆ’1k-1.

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 11. 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. i=0i = 0 or j=0j = 0), then dp[i][j] is the same value as the cell (i,j).

Obviously, if the cell (i,j) is 00, 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 O(1)\mathcal{O}(1) and since there are O(MN)\mathcal{O}(MN) cells, our time complexity is O(MN)\mathcal{O}(MN).

Time Complexity: O(MN)\mathcal{O}(MN)

Space Complexity

We store O(MN)\mathcal{O}(MN) cells in dp so our space complexity is O(MN)\mathcal{O}(MN).

Space Complexity: O(MN)\mathcal{O}(MN)

Bonus: We can use the space optimization mentioned in this article to optimize memory to O(N)O(N). Since we only use rows iβˆ’1i-1 and ii in dp to calculate dp values for row ii, we only need to maintain two rows of memory for dp, which is O(N)O(N).

C++ Solution

1class Solution {
2   public:
3    int countSquares(vector<vector<int>>& matrix) {
4        int m = matrix.size();
5        int n = matrix[0].size();  // dimensions for matrix
6        int ans = 0;
7        vector<vector<int>> dp(m, vector<int>(n));
8        for (int i = 0; i < m; i++) {
9            for (int j = 0; j < n; j++) {
10                if (i == 0 || j == 0) {  // cell is in first row or column
11                    dp[i][j] = matrix[i][j];
12                } else if (matrix[i][j] == 1) {
13                    dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
14                }
15                ans += dp[i][j];
16            }
17        }
18        return ans;
19    }
20};

Java Solution

1class Solution {
2    public int countSquares(int[][] matrix) {
3        int m = matrix.length;
4        int n = matrix[0].length; // dimensions for matrix
5        int[][] dp = new int[m][n];
6        int ans = 0;
7        for (int i = 0; i < m; i++) {
8            for (int j = 0; j < n; j++) {
9                if (i == 0 || j == 0) { // cell is in first row or column
10                    dp[i][j] = matrix[i][j];
11                } else if (matrix[i][j] == 1) {
12                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
13                }
14                ans += dp[i][j];
15            }
16        }
17        return ans;
18    }
19}

Python Solution

1class Solution:
2    def countSquares(self, matrix: List[List[int]]) -> int:
3        m = len(matrix)
4        n = len(matrix[0])  # dimensions for matrix
5        dp = [[0] * n for a in range(m)]
6        ans = 0
7        for i in range(m):
8            for j in range(n):
9                if i == 0 or j == 0:  # cell is in first row or column
10                    dp[i][j] = matrix[i][j]
11                elif matrix[i][j] == 1:
12                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
13                ans += dp[i][j]
14        return ans

Got a question?Β Ask the Teaching AssistantΒ anything you don't understand.

Still not clear? Ask in the Forum, Β DiscordΒ orΒ SubmitΒ the part you don't understand to our editors.

←
↑TA πŸ‘¨β€πŸ«