#1504

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count Submatrices With All Ones

Count Submatrices With All Ones is a dynamic programming problem focusing on submatrix counting using an efficient row-by-row approach.

array dynamic programming stack matrix monotonic stack

Problem Statement

Given an m x n binary matrix mat, your task is to return the number of submatrices that consist entirely of ones. Each submatrix is defined by its top-left and bottom-right corners. Submatrices can vary in size, and you must count all the possible submatrices that contain only 1s.

For example, consider the matrix mat = [[1,0,1],[1,1,0],[1,1,0]]. The task is to identify all the submatrices that contain only ones and return the total count. These submatrices include both smaller (1x1) and larger (2x2, 3x1) formations, requiring an efficient approach to avoid brute-force counting.

Examples

Example 1

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

Output: 13

There are 6 rectangles of side 1x1. There are 2 rectangles of side 1x2. There are 3 rectangles of side 2x1. There is 1 rectangle of side 2x2. There is 1 rectangle of side 3x1. Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.

Example 2

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

Output: 24

There are 8 rectangles of side 1x1. There are 5 rectangles of side 1x2. There are 2 rectangles of side 1x3. There are 4 rectangles of side 2x1. There are 2 rectangles of side 2x2. There are 2 rectangles of side 3x1. There is 1 rectangle of side 3x2. Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.

Constraints

1 <= m, n <= 150
mat[i][j] is either 0 or 1.

Solution Approach

State Transition Dynamic Programming

To solve this problem, we use a dynamic programming approach where each row's nums array tracks the length of consecutive ones at each position. This helps in efficiently calculating the number of submatrices by iterating over each row and leveraging the nums array to identify possible submatrices.

Building the `nums` Array

For each row i, the nums array is constructed such that nums[j] represents the number of consecutive ones ending at mat[i][j]. If mat[i][j] is 0, nums[j] is set to 0; otherwise, it is incremented by 1 from nums[j-1]. This preprocessing step simplifies the submatrix counting process.

Counting Submatrices

After constructing the nums array for each row, count the submatrices by iterating through the matrix and using the values in nums to determine the number of submatrices that can be formed from each position. This approach ensures that the solution is both time and space efficient.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this approach is O(m * n) due to the iteration over each element of the matrix, where m is the number of rows and n is the number of columns. The space complexity is O(n) as the nums array only requires storage for one row at a time.

What Interviewers Usually Probe

The candidate should demonstrate familiarity with dynamic programming and matrix manipulation techniques.
Look for a clear understanding of how to preprocess rows with the nums array to optimize the submatrix counting process.
Expect the candidate to discuss time and space complexities in the context of dynamic programming and matrix traversal.

Common Pitfalls or Variants

Common pitfalls

Failing to optimize the solution by using the nums array can lead to inefficient brute-force counting.
Overlooking the need for row-wise preprocessing of the matrix, which can hinder performance in larger test cases.
Misunderstanding the role of dynamic programming and treating the problem as a straightforward iteration over all submatrices.

Follow-up variants

The problem can be generalized to non-binary matrices, where elements may have different values.
A variant could involve considering rectangles instead of squares in submatrices.
In a more challenging variant, you might be asked to find submatrices with a sum equal to a given target rather than all ones.

FAQ

What is the main pattern to solve the Count Submatrices With All Ones problem?

The main pattern is state transition dynamic programming, where you preprocess each row into a nums array representing the count of consecutive ones.

How do you count submatrices in this problem?

Submatrices are counted by iterating through each row and using the nums array to determine the number of submatrices ending at each position.

What is the time complexity of solving Count 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.

Can this problem be optimized further?

Yes, the solution can be optimized using dynamic programming by avoiding brute-force submatrix counting and using row-wise preprocessing with the nums array.

What are some common mistakes when solving Count Submatrices With All Ones?

Common mistakes include not using dynamic programming for efficient row preprocessing and brute-forcing the submatrix counting process without optimizing with the nums array.

terminal

Solution

Solution 1: Enumeration + Prefix Sum

We can enumerate the bottom-right corner $(i, j)$ of the matrix, and then enumerate the first row $k$ upwards. The width of the matrix with $(i, j)$ as the bottom-right corner in each row is $\min_{k \leq i} \textit{g}[k][j]$, where $\textit{g}[k][j]$ represents the width of the matrix with $(k, j)$ as the bottom-right corner in the $k$-th row.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        g = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if mat[i][j]:
                    g[i][j] = 1 if j == 0 else 1 + g[i][j - 1]
        ans = 0
        for i in range(m):
            for j in range(n):
                col = inf
                for k in range(i, -1, -1):
                    col = min(col, g[k][j])
                    ans += col
        return ans

Continue Practicing

#1526 minimum number of increments on subarrays to form a target array #2617 minimum number of visited cells in a grid #1130 minimum cost tree from leaf values