Count Submatrices With All Ones

Count Submatrices With All Ones

What is this problem about?

The "Count Submatrices With All Ones interview question" is an extension of the "Count Square Submatrices" problem. You are given an $m imes n$ binary matrix and need to count ALL possible rectangular submatrices that consist only of ones. This includes squares, single cells, and long thin rectangles.

Why is this asked in interviews?

Meta and Bloomberg ask the "Count Submatrices With All Ones coding problem" to test a candidate's ability to reduce a 2D problem into a series of 1D problems. It requires knowledge of either monotonic stacks or specialized histograms. It is a classic "Dynamic Programming" and "Stack interview pattern" challenge that evaluations spatial reasoning.

Algorithmic pattern used

This problem follows the Histogram and Monotonic Stack pattern.

1. 1D Reduction: For each row $i$, treat it as the base of a histogram where the height of each column $j$ is the number of consecutive 1s ending at (i, j).
2. Histogram Calculation: height[i][j] = (matrix[i][j] == 1) ? height[i-1][j] + 1 : 0.
3. Counting Rectangles: For each row (histogram), the number of rectangles ending at (i, j) can be calculated using a monotonic stack. The stack maintains indices of increasing heights. The number of rectangles at $j$ is based on the height at $j$ and the "contributions" from smaller heights to its left.
4. Formula: total_rects[j] = height[j] * (j - prev_smaller_idx) + total_rects[prev_smaller_idx].

Example explanation

Matrix:

1 1
1 1

• Row 0: heights [1, 1]. Rectangles: [1, 2]. (Subarrays [1], [1], [1,1]). Sum = 3.
• Row 1: heights [2, 2]. Rectangles: [2, 4]. (Subarrays of height 1: 3; Subarrays of height 2: 3). Sum = 6. Total: 9.

Common mistakes candidates make

• $O(N^4)$ Brute Force: Trying to check every possible top-left and bottom-right corner.
• Incorrect Stack Logic: Failing to account for the "shared" rectangles when multiple adjacent columns have the same height.
• Memory usage: Not reusing the height array across rows, which uses extra $O(M imes N)$ space.

Interview preparation tip

This problem is very similar to "Largest Rectangle in Histogram." If you master the monotonic stack for histograms, you can solve many "Hard" matrix problems. Always remember: "A matrix is just a stack of histograms."