Count Submatrices With All Ones

Problem

Given an m x n binary matrix mat, return the number ofsubmatrices that have all ones.

Examples

Example 1

Input: mat = [[1,0,1],[1,1,0],[1,1,0]]
Output: 13
Explanation: 
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
Explanation: 
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

Method 1 – Histogram + Monotonic Stack

Intuition

We can treat each row as the base of a histogram, where the height at each column is the number of consecutive ones above (including the current row). For each row, we use a monotonic stack to efficiently count the number of submatrices ending at that row.

Approach

1. For each row, update the histogram heights for each column.
2. For each row, use a monotonic stack to count the number of rectangles ending at each column:
   1. For each column, pop from the stack until the top is less than the current height.
   2. The width is the distance to the previous smaller height.
   3. The number of submatrices ending at (i, j) is the height times the width, plus the count from the previous smaller height.
3. Sum the counts for all positions.
4. Return the total count.

Code

C++

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size(), ans = 0;
        vector<int> h(n);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j)
                h[j] = mat[i][j] ? h[j] + 1 : 0;
            vector<int> stack, sum(n);
            for (int j = 0; j < n; ++j) {
                while (!stack.empty() && h[stack.back()] >= h[j]) stack.pop_back();
                if (!stack.empty()) {
                    int prev = stack.back();
                    sum[j] = sum[prev] + h[j] * (j - prev);
                } else {
                    sum[j] = h[j] * (j + 1);
                }
                ans += sum[j];
                stack.push_back(j);
            }
        }
        return ans;
    }
};

Go

func numSubmat(mat [][]int) int {
    m, n := len(mat), len(mat[0])
    h := make([]int, n)
    ans := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if mat[i][j] == 1 {
                h[j]++
            } else {
                h[j] = 0
            }
        }
        stack, sum := []int{}, make([]int, n)
        for j := 0; j < n; j++ {
            for len(stack) > 0 && h[stack[len(stack)-1]] >= h[j] {
                stack = stack[:len(stack)-1]
            }
            if len(stack) > 0 {
                prev := stack[len(stack)-1]
                sum[j] = sum[prev] + h[j]*(j-prev)
            } else {
                sum[j] = h[j]*(j+1)
            }
            ans += sum[j]
            stack = append(stack, j)
        }
    }
    return ans
}

Java

class Solution {
    public int numSubmat(int[][] mat) {
        int m = mat.length, n = mat[0].length, ans = 0;
        int[] h = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++)
                h[j] = mat[i][j] == 1 ? h[j] + 1 : 0;
            int[] stack = new int[n], sum = new int[n];
            int top = -1;
            for (int j = 0; j < n; j++) {
                while (top >= 0 && h[stack[top]] >= h[j]) top--;
                if (top >= 0) {
                    int prev = stack[top];
                    sum[j] = sum[prev] + h[j] * (j - prev);
                } else {
                    sum[j] = h[j] * (j + 1);
                }
                ans += sum[j];
                stack[++top] = j;
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun numSubmat(mat: Array<IntArray>): Int {
        val m = mat.size; val n = mat[0].size
        val h = IntArray(n)
        var ans = 0
        for (i in 0 until m) {
            for (j in 0 until n) h[j] = if (mat[i][j] == 1) h[j] + 1 else 0
            val stack = mutableListOf<Int>()
            val sum = IntArray(n)
            for (j in 0 until n) {
                while (stack.isNotEmpty() && h[stack.last()] >= h[j]) stack.removeAt(stack.size-1)
                if (stack.isNotEmpty()) {
                    val prev = stack.last()
                    sum[j] = sum[prev] + h[j] * (j - prev)
                } else {
                    sum[j] = h[j] * (j + 1)
                }
                ans += sum[j]
                stack.add(j)
            }
        }
        return ans
    }
}

Python

class Solution:
    def numSubmat(self, mat: list[list[int]]) -> int:
        m, n = len(mat), len(mat[0])
        h = [0] * n
        ans = 0
        for i in range(m):
            for j in range(n):
                h[j] = h[j] + 1 if mat[i][j] else 0
            stack, sum_ = [], [0] * n
            for j in range(n):
                while stack and h[stack[-1]] >= h[j]:
                    stack.pop()
                if stack:
                    prev = stack[-1]
                    sum_[j] = sum_[prev] + h[j] * (j - prev)
                else:
                    sum_[j] = h[j] * (j + 1)
                ans += sum_[j]
                stack.append(j)
        return ans

Rust

impl Solution {
    pub fn num_submat(mat: Vec<Vec<i32>>) -> i32 {
        let m = mat.len();
        let n = mat[0].len();
        let mut h = vec![0; n];
        let mut ans = 0;
        for i in 0..m {
            for j in 0..n {
                h[j] = if mat[i][j] == 1 { h[j] + 1 } else { 0 };
            }
            let mut stack = vec![];
            let mut sum = vec![0; n];
            for j in 0..n {
                while let Some(&last) = stack.last() {
                    if h[last] >= h[j] { stack.pop(); } else { break; }
                }
                if let Some(&prev) = stack.last() {
                    sum[j] = sum[prev] + h[j] * (j - prev) as i32;
                } else {
                    sum[j] = h[j] * (j + 1) as i32;
                }
                ans += sum[j];
                stack.push(j);
            }
        }
        ans
    }
}

TypeScript

class Solution {
    numSubmat(mat: number[][]): number {
        const m = mat.length, n = mat[0].length;
        const h = Array(n).fill(0);
        let ans = 0;
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++)
                h[j] = mat[i][j] ? h[j] + 1 : 0;
            const stack: number[] = [], sum: number[] = Array(n).fill(0);
            for (let j = 0; j < n; j++) {
                while (stack.length && h[stack[stack.length-1]] >= h[j]) stack.pop();
                if (stack.length) {
                    const prev = stack[stack.length-1];
                    sum[j] = sum[prev] + h[j] * (j - prev);
                } else {
                    sum[j] = h[j] * (j + 1);
                }
                ans += sum[j];
                stack.push(j);
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(m * n), since we process each cell once per row.
• 🧺 Space complexity: O(n), for the histogram and stack per row.