Problem Description

Given a binary matrix matrix of size m x n, where each element is either 0 or 1, your task is to count the number of submatrices that contain only 1s. A submatrix is any contiguous rectangular area within the matrix, and all its elements must be 1s for it to be counted. The elements of the matrix cannot be reused across different submatrices, but overlapping is allowed as long as each counted submatrix is a distinct rectangle of 1s.

• Input: matrix (a list of lists, each containing 0 or 1)
• Output: An integer representing the total number of submatrices where every element is 1
• Constraints: 1 <= m, n <= 150; Each element is either 0 or 1

Thought Process

The naive way to solve this problem is to check every possible submatrix and count those that consist only of 1s. However, this approach is highly inefficient for larger matrices, as the number of possible submatrices grows rapidly with the matrix size.

To optimize, we need to avoid redundant work. Instead of checking every possible rectangle, we can use dynamic programming or a histogram-based approach to efficiently count the valid submatrices. The key insight is that for each cell, we can determine how many submatrices end at that cell by considering the number of consecutive 1s above it and to its left.

The process involves:

• Building up information row by row (like a histogram)
• For each cell, using previous computations to quickly count how many submatrices of all 1s end at that cell
• Summing across all cells for the final answer

Solution Approach

We use a dynamic programming and histogram approach to efficiently count submatrices with all ones:

1. Build Row-wise Histograms:
   • For each cell matrix[i][j], compute heights[i][j] as the number of consecutive 1s in the column above (including itself).
   • If matrix[i][j] == 0, set heights[i][j] = 0.
2. Count Submatrices Ending at Each Cell:
   • For each row, for each column, treat heights[i][j] as the height of a histogram bar.
   • For each cell, look leftwards (to previous columns in the same row), keeping track of the minimum height seen so far.
   • Each time you find a minimum height, add it to a running total (since each rectangle formed by heights up to that point is a valid submatrix of all 1s).
3. Sum All Counts:
   • Repeat the above for every cell, summing up the counts to get the total number of submatrices with all 1s.

This approach avoids redundant checks and leverages previously computed values, making it much more efficient than brute force.

Example Walkthrough

Consider the following input matrix:

    matrix = [
      [1, 0, 1],
      [1, 1, 0],
      [1, 1, 0]
    ]
  

1. Compute heights:
   • Row 0: [1, 0, 1]
   • Row 1: [2, 1, 0]
   • Row 2: [3, 2, 0]
2. Counting for each cell:
   • Row 0: cell (0,0): height=1, left=1 → add 1
   • Row 0: cell (0,2): height=1, left=1 → add 1
   • Row 1: cell (1,0): height=2, left=2 → add 2
   • Row 1: cell (1,1): height=1, left=1 → add 2 (height=1 for (1,1), height=1 for (1,0)-(1,1))
   • Row 2: cell (2,0): height=3, left=3 → add 3
   • Row 2: cell (2,1): height=2, left=2 → add 4 (height=2 for (2,1), height=2 for (2,0)-(2,1))
3. Sum up:
   • 1 (0,0) + 1 (0,2) + 2 (1,0) + 2 (1,1) + 3 (2,0) + 4 (2,1) = 13

So, the answer is 13.

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(m³ n³) — since you must consider every possible rectangle and check every element inside it.
• Space Complexity: O(1) — only a few variables needed.

• Time Complexity: O(m * n * n) — for each row, for each column, we may look leftward up to n times (though with further optimizations, this can be improved, but this is the straightforward implementation).
• Space Complexity: O(m * n) — for the height matrix.

The optimized approach is much faster and feasible for the largest allowed input sizes.

Summary

By transforming each row into a histogram of consecutive 1s and efficiently counting the number of submatrices ending at each cell, we can solve the "Count Submatrices With All Ones" problem in a much more efficient way than brute force. The key insight is to use dynamic programming to build up solutions from previous rows and columns, leveraging the structure of the matrix to avoid redundant work. This approach is elegant, scalable, and highlights the power of reusing computations in 2D problems.

Code Implementation

class Solution:
    def numSubmat(self, matrix):
        m, n = len(matrix), len(matrix[0])
        heights = [[0]*n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if matrix[i][j]:
                    heights[i][j] = heights[i-1][j] + 1 if i > 0 else 1
        res = 0
        for i in range(m):
            for j in range(n):
                min_h = heights[i][j]
                for k in range(j, -1, -1):
                    if heights[i][k] == 0:
                        break
                    min_h = min(min_h, heights[i][k])
                    res += min_h
        return res
      

class Solution {
public:
    int numSubmat(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> heights(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j]) {
                    heights[i][j] = (i > 0 ? heights[i-1][j] : 0) + 1;
                }
            }
        }
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int min_h = heights[i][j];
                for (int k = j; k >= 0 && heights[i][k] > 0; --k) {
                    min_h = min(min_h, heights[i][k]);
                    res += min_h;
                }
            }
        }
        return res;
    }
};
      

class Solution {
    public int numSubmat(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] heights = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 1) {
                    heights[i][j] = (i > 0 ? heights[i-1][j] : 0) + 1;
                }
            }
        }
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int min_h = heights[i][j];
                for (int k = j; k >= 0 && heights[i][k] > 0; --k) {
                    min_h = Math.min(min_h, heights[i][k]);
                    res += min_h;
                }
            }
        }
        return res;
    }
}
      

var numSubmat = function(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const heights = Array.from({length: m}, () => Array(n).fill(0));
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (matrix[i][j]) {
                heights[i][j] = (i > 0 ? heights[i-1][j] : 0) + 1;
            }
        }
    }
    let res = 0;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            let min_h = heights[i][j];
            for (let k = j; k >= 0 && heights[i][k] > 0; --k) {
                min_h = Math.min(min_h, heights[i][k]);
                res += min_h;
            }
        }
    }
    return res;
};