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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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].

  1. 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

1class Solution:
2    def numSubmat(self, mat: List[List[int]]) -> int:
3        # Get the number of rows (m) and columns (n) of the matrix.
4        num_rows, num_cols = len(mat), len(mat[0])
5      
6        # Initialize a matrix to store the number of continuous ones in each row.
7        continuous_ones = [[0] * num_cols for _ in range(num_rows)]
8      
9        # Populate the continuous_ones matrix.
10        for row in range(num_rows):
11            for col in range(num_cols):
12                # If we encounter a '1', count the continuous ones. If in first column,
13                # it can only be 1 or 0. Otherwise, add 1 to the left cell's count.
14                if mat[row][col]:
15                    continuous_ones[row][col] = 1 if col == 0 else 1 + continuous_ones[row][col - 1]
16      
17        # Initialize a count for total number of submatrices.
18        total_submatrices = 0
19      
20        # Calculate the number of submatrices for each cell as the bottom-right corner.
21        for row in range(num_rows):
22            for col in range(num_cols):
23                # This will keep track of the smallest number of continuous ones in the current column,
24                # up to the current row 'row'.
25                min_continuous_ones = float('inf')
26              
27                # Travel up the rows from the current cell.
28                for k in range(row, -1, -1):
29                    # Find the smallest number of continuous ones in this column up to the k-th row.
30                    min_continuous_ones = min(min_continuous_ones, continuous_ones[k][col])
31                  
32                    # Add the smallest number to the total count.
33                    total_submatrices += min_continuous_ones
34      
35        # Return the total number of submatrices.
36        return total_submatrices
37
1class Solution {
2
3    // Method to count the number of submatrices with all ones
4    public int numSubmat(int[][] mat) {
5        int rows = mat.length; // the number of rows in given matrix
6        int cols = mat[0].length; // the number of columns in given matrix
7        int[][] width = new int[rows][cols]; // buffer to store the width of consecutive ones ending at (i, j)
8      
9        // Compute the width matrix
10        for (int i = 0; i < rows; ++i) {
11            for (int j = 0; j < cols; ++j) {
12                // If the cell contains a '1', calculate the width
13                if (mat[i][j] == 1) {
14                    width[i][j] = (j == 0) ? 1 : 1 + width[i][j - 1];
15                }
16                // '0' cells are initialized as zero, no need to explicitly set them
17            }
18        }
19      
20        int count = 0; // variable to accumulate the count of submatrices
21
22        // For each position in the matrix, calculate the number of submatrices
23        // that can be formed ending at (i, j)
24        for (int i = 0; i < rows; ++i) {
25            for (int j = 0; j < cols; ++j) {
26                // Start with a large number to minimize with the width of rows above
27                int minWidth = Integer.MAX_VALUE;
28                // Move up from row 'i' to '0' and calculate the minWidth for submatrices ending at (i, j)
29                for (int k = i; k >= 0 && minWidth > 0; --k) {
30                    minWidth = Math.min(minWidth, width[k][j]);
31                    count += minWidth; // accumulate the count with the current minWidth
32                }
33            }
34        }
35      
36        return count; // returning the total count of submatrices
37    }
38}
39
1class Solution {
2public:
3    int numSubmat(vector<vector<int>>& mat) {
4        int rows = mat.size(), cols = mat[0].size(); // dimensions of the matrix
5        vector<vector<int>> width(rows, vector<int>(cols, 0)); // 2D vector to track the width of '1's ending at mat[i][j]
6
7        // Pre-calculate the width of the continuous '1's in each row, left to right
8        for (int row = 0; row < rows; ++row) {
9            for (int col = 0; col < cols; ++col) {
10                if (mat[row][col] == 1) {
11                    width[row][col] = col == 0 ? 1 : 1 + width[row][col - 1];
12                }
13                // if mat[row][col] is 0, width[row][col] stays 0, which was set initially
14            }
15        }
16
17        int totalCount = 0; // count of all possible submatrices
18
19        // Main logic to find the total number of submatrices with 1
20        for (int topRow = 0; topRow < rows; ++topRow) {
21            for (int col = 0; col < cols; ++col) {
22                int minWidth = INT_MAX; // set minWidth to maximum possible value initially
23                // Evaluate bottom-up for each submatrix
24                for (int bottomRow = topRow; bottomRow >= 0 && minWidth > 0; --bottomRow) {
25                    minWidth = min(minWidth, width[bottomRow][col]); // find minimal width of '1's column-wise
26                    totalCount += minWidth; // Add the minimum width to the totalCount
27                }
28            }
29        } 
30
31        return totalCount; // Return the final totalCount of all submatrices
32    }
33};
34
1function numSubmat(mat: number[][]): number {
2    const rows = mat.length; // number of rows in the matrix
3    const cols = mat[0].length; // number of columns in the matrix
4    let width: number[][] = new Array(rows).fill(0).map(() => new Array(cols).fill(0)); // create 2D array for tracking continuous '1's width for each cell
5
6    // Pre-calculate the width of continuous '1's for each cell in the row
7    for (let row = 0; row < rows; ++row) {
8        for (let col = 0; col < cols; ++col) {
9            if (mat[row][col] === 1) {
10                width[row][col] = col === 0 ? 1 : width[row][col - 1] + 1;
11                // If mat[row][col] is 1, either start a new sequence of '1's or extend the current sequence
12            }
13            // If mat[row][col] is 0, width stays 0 (array initialized with 0's)
14        }
15    }
16
17    let totalCount = 0; // Initialize count of all possible submatrices
18
19    // Iterate through each cell in the matrix to calculate submatrices
20    for (let topRow = 0; topRow < rows; ++topRow) {
21        for (let col = 0; col < cols; ++col) {
22            let minWidth = Number.MAX_SAFE_INTEGER; // Set minWidth to a high value (safe integer limit)
23
24            // Iterate bottom-up to calculate all possible submatrices for each cell
25            for (let bottomRow = topRow; bottomRow >= 0 && minWidth > 0; --bottomRow) {
26                minWidth = Math.min(minWidth, width[bottomRow][col]); // Update minWidth column-wise for the current submatrix
27                totalCount += minWidth; // Accumulate the count of 1's for this submatrix width
28            }
29        }
30    }
31
32    return totalCount; // Return the total count of submatrices with all 1's
33}
34
35// Example use:
36// const matrix = [[1, 0, 1], [1, 1, 0], [1, 1, 0]];
37// console.log(numSubmat(matrix)); // Output will depend on the provided matrix
38

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following shows the order of node visit in a Breadth-first Search?


Recommended Readings

Got a question? Ask the Monster 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.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄