Count Submatrices With All Ones

Medium
1406.

Count Submatrices With All Ones

Count Submatrices With All Ones is a medium coding problem on arrays, matrix and stack, asked in Amazon and Google interviews.

Given an m x n binary matrix mat, count its submatrices (axis-aligned rectangles of cells, of any size from 1 x 1 up to m x n) in which every cell is 1.

Example 1

Input
mat = [[1,1],[1,1]]
Output
9
Explanation
Four 1×1, two 1×2, two 2×1 and one 2×2.

Example 2

Input
mat = [[1,0,1],[0,1,1]]
Output
6
Explanation
Four 1×1, the 1×2 in the bottom row and the 2×1 in the last column.

Example 3

Input
mat = [[0]]
Output
0

Constraints

  • 1 <= m, n <= 150
  • mat[i][j] is 0 or 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} mat
 * @return {number}
 */
var numSubmat = function(mat) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Submatrices With All Ones — Problem & Solution

Count Submatrices With All Ones solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Submatrices With All Ones is a medium coding problem on arrays, matrix and stack, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Matrix, Stack, Monotonic Stack
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an m x n binary matrix mat, count its submatrices (axis-aligned rectangles of cells, of any size from 1 x 1 up to m x n) in which every cell is 1.

Example 1

Input: mat = [[1,1],[1,1]]
Output: 9
Explanation: Four 1×1, two 1×2, two 2×1 and one 2×2.

Example 2

Input: mat = [[1,0,1],[0,1,1]]
Output: 6
Explanation: Four 1×1, the 1×2 in the bottom row and the 2×1 in the last column.

Example 3

Input: mat = [[0]]
Output: 0

Constraints

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

Hints for Count Submatrices With All Ones

  1. Hint 1

    Count rectangles by their bottom-right corner. Fix the bottom row and look up: each column has a height of consecutive 1s ending at that row.

  2. Hint 2

    For bottom-right corner (r, c), the number of all-ones rectangles is the sum over left columns k <= c of min(h[k..c]).

  3. Hint 3

    That running-minimum sum is what a monotonic stack computes: with p the previous column whose height is smaller than h[c], count[c] = count[p] + h[c] × (c - p).

How to solve Count Submatrices With All Ones

Turn each row into a histogram of upward runs of 1s; the rectangles with their bottom-right corner at (r, c) number Σ min(h[k..c]) over left edges k, which a monotonic stack maintains in O(1) amortised per cell.

Approach

  1. Keep h[c], the number of consecutive 1s ending at the current row in column c (reset to 0 on a 0).
  2. For each row, sweep the columns left to right with a stack of column indices of strictly increasing height.
  3. Pop while the top's height is >= h[c]. If a column p remains, count[c] = count[p] + h[c] × (c - p); otherwise count[c] = h[c] × (c + 1).
  4. Add count[c] to the total and push c.

Why it works

A rectangle with bottom-right corner (r, c) and left column k can be any height up to min(h[k..c]), so that is how many there are. For left columns between p + 1 and c the minimum is h[c] itself (they are all at least as tall), giving h[c] × (c - p); for left columns <= p the minimum over [k, c] equals the minimum over [k, p] because h[p] < h[c], which is exactly count[p].

Complexity

  • Time — O(m · n)
  • Space — O(n)

Pitfalls

  • Counting only squares, or only full-width rows, misses most rectangles.
  • Reset h[c] to 0 on a 0 cell — heights are consecutive runs, not column totals.
  • An O(m² · n²) enumeration with prefix sums is correct but too slow at 150 × 150.

Reference solution

Python

from typing import List

def numSubmat(mat: List[List[int]]) -> int:
    m, n = len(mat), len(mat[0])
    h = [0] * n
    total = 0
    for r in range(m):
        for c in range(n):
            h[c] = h[c] + 1 if mat[r][c] == 1 else 0
        cnt = [0] * n
        st = []
        for c in range(n):
            while st and h[st[-1]] >= h[c]:
                st.pop()
            if st:
                p = st[-1]
                cnt[c] = cnt[p] + h[c] * (c - p)
            else:
                cnt[c] = h[c] * (c + 1)
            total += cnt[c]
            st.append(c)
    return total

Java

public static int numSubmat(int[][] mat) {
    int m = mat.length, n = mat[0].length;
    int[] h = new int[n], cnt = new int[n], st = new int[n];
    int total = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) h[c] = mat[r][c] == 1 ? h[c] + 1 : 0;
        int top = 0;
        for (int c = 0; c < n; c++) {
            while (top > 0 && h[st[top - 1]] >= h[c]) top--;
            if (top > 0) {
                int p = st[top - 1];
                cnt[c] = cnt[p] + h[c] * (c - p);
            } else {
                cnt[c] = h[c] * (c + 1);
            }
            total += cnt[c];
            st[top++] = c;
        }
    }
    return total;
}

C++

int numSubmat(vector<vector<int>>& mat) {
    int m = mat.size(), n = mat[0].size();
    vector<int> h(n, 0), cnt(n, 0), st;
    int total = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) h[c] = mat[r][c] == 1 ? h[c] + 1 : 0;
        st.clear();
        for (int c = 0; c < n; c++) {
            while (!st.empty() && h[st.back()] >= h[c]) st.pop_back();
            if (!st.empty()) {
                int p = st.back();
                cnt[c] = cnt[p] + h[c] * (c - p);
            } else {
                cnt[c] = h[c] * (c + 1);
            }
            total += cnt[c];
            st.push_back(c);
        }
    }
    return total;
}

JavaScript

var numSubmat = function(mat) {
    var m = mat.length, n = mat[0].length;
    var h = new Array(n).fill(0);
    var total = 0;
    for (var r = 0; r < m; r++) {
        for (var c = 0; c < n; c++) h[c] = mat[r][c] === 1 ? h[c] + 1 : 0;
        var cnt = new Array(n).fill(0);
        var st = [];
        for (var c2 = 0; c2 < n; c2++) {
            while (st.length > 0 && h[st[st.length - 1]] >= h[c2]) st.pop();
            if (st.length > 0) {
                var p = st[st.length - 1];
                cnt[c2] = cnt[p] + h[c2] * (c2 - p);
            } else {
                cnt[c2] = h[c2] * (c2 + 1);
            }
            total += cnt[c2];
            st.push(c2);
        }
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal