#1277

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count Square Submatrices with All Ones

Count the number of square submatrices with all ones in a given binary matrix using dynamic programming.

Problem Statement

Given a binary matrix of size m * n, where each element is either 0 or 1, your task is to find the total number of square submatrices that are filled entirely with ones. The submatrices can vary in size, and each square submatrix must have all elements equal to 1.

For example, in a matrix where 1's form several overlapping squares, you need to calculate how many such submatrices exist. This includes counting the submatrices of different sizes, such as 1x1, 2x2, 3x3, etc., as long as all elements in the submatrix are ones.

Examples

Example 1

Input: matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ]

Output: 15

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

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 Approach

Dynamic Programming Table

Create a 2D dynamic programming table where each entry dp[i][j] represents the side length of the largest square submatrix that ends at position (i, j). The recurrence relation is: if matrix[i][j] == 1, then dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. If matrix[i][j] == 0, dp[i][j] = 0.

Iterating Over the Matrix

Iterate through each element of the matrix and update the DP table. For each element that is a 1, calculate the size of the largest square submatrix with its bottom-right corner at that element. Sum the values in the DP table to get the total count of square submatrices.

Space Optimization

To optimize space, we can use a 1D array instead of a 2D DP table. This can be done by maintaining only the current and previous rows, reducing the space complexity from O(m*n) to O(n).

Complexity Analysis

Metric	Value
Time	O(row \cdot col)
Space	O(col)

The time complexity of the solution is O(m * n), where m is the number of rows and n is the number of columns in the matrix, since we are iterating through each element once. The space complexity can be optimized to O(n) by using a 1D array to store the DP values of the current row and the previous row.

What Interviewers Usually Probe

The candidate should demonstrate understanding of dynamic programming and how state transition works in this context.
Look for awareness of space optimization techniques, particularly reducing a 2D DP table to 1D.
The ability to handle edge cases, such as matrices with no ones or matrices that are very large, will indicate strong problem-solving skills.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the recurrence relation and incorrectly calculating the DP values.
Failing to optimize space complexity, leading to excessive memory usage.
Not summing the values in the DP table correctly to count the total number of square submatrices.

Follow-up variants

Matrix with larger dimensions (e.g., 500x500) to test efficiency and space optimization.
Matrix where all elements are 1, which will test if the DP approach can correctly count all possible submatrices.
Matrix with random placements of 1's and 0's to ensure robustness of the solution under various configurations.

FAQ

What is the key idea behind solving the Count Square Submatrices with All Ones problem?

The key idea is to use dynamic programming to calculate the size of the largest square submatrix ending at each position in the matrix and sum these values.

How can space complexity be optimized in this problem?

Space complexity can be optimized by reducing the 2D DP table to a 1D array, maintaining only the current and previous rows of the matrix.

What are the edge cases to consider in this problem?

Edge cases include matrices with no ones (resulting in 0 squares), and matrices where all elements are 1 (resulting in the maximum number of square submatrices).

How does the dynamic programming approach work in the Count Square Submatrices with All Ones problem?

The dynamic programming approach builds a table where each entry represents the side length of the largest square that can be formed with its bottom-right corner at that element, iterating through the matrix to accumulate the total number of square submatrices.

What is the time complexity of the solution for Count Square Submatrices with All Ones?

The time complexity is O(m * n), where m is the number of rows and n is the number of columns in the matrix, as we need to iterate through each element once.

terminal

Solution

Solution 1: 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]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        f = [[0] * n for _ in range(m)]
        ans = 0
        for i, row in enumerate(matrix):
            for j, v in enumerate(row):
                if v == 0:
                    continue
                if i == 0 or j == 0:
                    f[i][j] = 1
                else:
                    f[i][j] = min(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1]) + 1
                ans += f[i][j]
        return ans

Continue Practicing

#1289 minimum falling path sum ii #1301 number of paths with max score #1349 maximum students taking exam