Count Submatrices With All Ones - Video Solutions

Problem Overview: Given a binary matrix, count how many submatrices contain only 1s. Every possible rectangle inside the matrix must be checked, but doing that naively is too slow. The key observation: each row can be treated like the base of a histogram representing consecutive vertical ones.

Approach 1: Dynamic Programming with Upward Expansion (O(m * n^2) time, O(n) space)

Build a DP array where dp[r][c] represents the number of consecutive 1s ending at (r, c) horizontally. For each cell containing 1, treat it as the bottom-right corner of potential submatrices. Move upward row by row while maintaining the minimum width of consecutive ones seen so far. Add this width to the answer at every step because it represents how many valid submatrices end at that row. The approach uses ideas from dynamic programming and works well for moderate matrix sizes.

Approach 2: Histogram + Monotonic Stack (O(m * n) time, O(n) space)

Convert each row into a histogram where height[c] counts consecutive vertical ones up to that row. The problem becomes counting how many submatrices end at the current row using this histogram. Use a monotonic stack to efficiently calculate the number of rectangles contributed by each column while maintaining increasing heights. When a smaller height appears, pop taller bars and adjust the count of rectangles they contributed. This avoids rechecking previous columns and ensures each element is pushed and popped at most once.

The histogram view transforms the 2D problem into repeated 1D rectangle counting. Combined with stack-based range aggregation, it reduces redundant computations across columns. This pattern commonly appears in matrix problems where vertical accumulation converts 2D constraints into histogram problems.

Recommended for interviews: The histogram + monotonic stack solution is the expected optimal answer with O(m * n) time. The DP approach is easier to derive and shows understanding of submatrix expansion, but the stack-based histogram technique demonstrates stronger algorithmic depth and familiarity with advanced array processing patterns.