1504. Count Submatrices With All Ones

Problem Description

The problem presents a m x n binary matrix mat, where m represents the number of rows and n represents the number of columns. A binary matrix is a matrix where each element is either 0 or 1. Our task is to count the number of unique submatrices within this matrix where every element is 1. A submatrix is defined as any contiguous block of cells within the larger matrix, and it could be as small as a single cell or as large as the entire matrix, as long as all its elements are '1's.

Intuition

To solve this problem, an intuitive approach is to look at each cell and ask, "How many submatrices, for which this cell is the bottom-right corner, contain all ones?" By answering this question for every cell, we can sum these counts to find the total number of submatrices that have all ones.

To efficiently compute the count for each cell, we can use a dynamic programming approach, where we keep a running count of consecutive '1's in each row up to and including the current cell. This count will reset to 0 whenever we encounter a '0' as we go left to right in each row. This helps because the number of submatrices for which a cell is the bottom-right corner depends on the number of consecutive '1's to the left of that cell (in the same row) and above it (in the same column).

With this running count, we iterate over each cell (let's say at position (i, j)), and for each cell we look upwards, tracking the minimum number of consecutive '1's seen so far in the column. The number of submatrices that use the cell (i, j) as the bottom-right corner is the sum of these minimum values, because the submatrix size is constrained by the smallest count of consecutive '1's in any row above (i, j) including the row containing (i, j).

By incrementing our answer with these counts for each cell, we end up with the total number of submatrices that have all ones.

Learn more about Stack, Dynamic Programming and Monotonic Stack patterns.

Solution Approach

The solution provided is a dynamic programming approach that optimizes the brute force method. The code uses an auxiliary grid g with the same dimensions as the input matrix mat. Here's a step-by-step breakdown of the approach:

1. Create a running count grid: We initialize a grid g such that g[i][j] represents the number of consecutive '1's ending at position (i, j) in the matrix mat. This is calculated by iterating through each row of mat. If mat[i][j] is a '1', then g[i][j] is set to 1 + g[i][j - 1] if j is not 0, otherwise it's set to 1. If mat[i][j] is '0', g[i][j] remains 0.

2. Iterate over all cells to count submatrices: For every cell (i, j) in the matrix, we perform the following steps:

   • Initialize col to infinity to keep track of the smallest number of consecutive '1's found so far in the current column.
   • Move upwards from the current cell (i, j) to the top of the column (0, j), updating col to be the minimum of its current value and g[k][j] where k ranges from i to 0. This represents the number of consecutive '1's in column j at row k.
   • Add the value of col to ans for every row above (and including) the current cell. This adds the number of submatrices where cell (i, j) is the bottom-right corner, as explained in the intuition.

The data structures used are:

• An input matrix mat of size m x n, where mat[i][j] represents a cell in the original binary matrix.
• An auxiliary grid g of the same size as mat, where g[i][j] stores the number of consecutive '1's to the left of mat[i][j].

The patterns and algorithms used include dynamic programming, to keep track of the running count of '1's in a row (state), and for each state, we calculate the maximum number of submatrices that can be formed using the bottom edge of that submatrix. This involves iterating upwards and finding the width (consecutive '1's) that is limiting the size of the submatrix.

In terms of complexity, the algorithm uses O(m*n) space for the grid g and O(m^2 * n) time, since it iterates through the matrix and for each cell, it potentially iterates through m elements above it in the column.

Example Walkthrough

Let's demonstrate the solution approach using a small example with a 3x3 binary matrix mat as input:

1mat = [
2    [1, 0, 1],
3    [1, 1, 1],
4    [0, 1, 0]
5]

Following the dynamic programming approach, here's how we would walk through this instance step-by-step.

1. Create a running count grid (g): We go through each row and build our auxiliary grid g. For the given matrix mat, g would look like this:

1g = [
2    [1, 0, 1],
3    [1, 2, 3],
4    [0, 1, 0]
5]

Element g[1][2] is 3 because there are three consecutive 1s ending at mat[1][2].

2. Iterate over all cells to count submatrices:
   • For cell (0, 0) in mat, the count of submatrices for which it is the bottom-right corner is just 1. Update ans = 1.
   • Cell (0, 1) is 0, so it cannot be the bottom-right corner of any submatrix with all 1s. ans remains 1.
   • Cell (0, 2) can only be the bottom-right corner of a submatrix with size 1x1. Update ans = 1 + 1 = 2.
   • Cell (1, 0) can be the bottom-right corner of two submatrices: two of size 1x1 (mat[1][0] and mat[0][0]), so update ans = 2 + 2 = 4.
   • Cell (1, 1) is interesting; it can be the bottom-right corner of one submatrix of size 2x2, two submatrices of size 2x1 (above it), and an additional two submatrices of size 1x1 (same row). Update ans = 4 + 5 = 9.
   • For cell (1, 2), the limiting factor is the 0 in cell (0, 1). Thus, it can only form one submatrix of size 1x3 and three submatrices of size 1x1. Hence, we update ans = 9 + 4 = 13.
   • Skip cell (2, 0) as it is 0.
   • Cell (2, 1) can form one submatrix of size 1x1. Update ans = 13 + 1 = 14.
   • Skip cell (2, 2) as it is 0.

Thus, the final answer, the number of unique submatrices where every element is 1, is 14 for the provided mat matrix.

In terms of data structures and patterns:

• The input matrix mat represents the original binary matrix.
• The auxiliary grid g helps to calculate how many 1s we have consecutively to the left of a given cell, including the cell itself, which saves us time when checking the possibilities of forming submatrices.

The space complexity remains O(m*n) which is required for storing the grid g, and the time complexity is O(m^2 * n) due to the nested iterations used for each element to consider the cells above it. For larger matrices, this complexity is something to be aware of as it could become a performance bottleneck.

Solution Implementation

Time and Space Complexity

The input matrix is of size m x n. Let's analyze the time and space complexity:

Time Complexity:

1. The first double for loop where the matrix g is being populated runs in O(m * n) time as it visits each element once.

2. The nested triple for loop structure calculates the number of submatrices. For each element mat[i][j], we are going upwards and counting the number of rectangles ending at that cell. This part has a worst-case time complexity of O(m * n * m) because for each element in the matrix (m * n), we are potentially traveling upwards to the start of the column (m).

Thus, the total time complexity is O(m * n + m * n * m) which simplifies to O(m^2 * n).

Space Complexity:

1. We have an auxiliary matrix g the same size as the input matrix which takes O(m * n) space.

2. Variables col and ans use a constant amount of extra space, O(1).

The total space complexity of the algorithm is O(m * n) due to the auxiliary matrix g.

Learn more about how to find time and space complexity quickly using problem constraints.