Skip to main content
Talentd

Count Submatrices With All Ones - Solution & Explanation

MediumArrayDynamic ProgrammingStackMatrix12 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

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

 

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.

Approach Overview

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.

Approach 1: Histogram Approach

This approach converts each row of the matrix into a histogram by counting the number of continuous '1's above each cell, including the current cell. We then calculate the number of submatrices ending at each position using a monotonic stack to manage heights in order to calculate the width of possible rectangles.

This solution iterates over each possible row and calculates heights of histograms ending at each row. It uses a stack to efficiently count submatrices.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(m * n^2), where m is the number of rows and n is the number of columns. Space Complexity: O(n) for the height and stack arrays.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

Utilize dynamic programming to store the count of submatrices ending at each position (i, j). This solution leverages cumulative sums to efficiently count submatrices.

This C++ solution uses a 2D dynamic programming table to count the number of possible submatrices that can end at each cell and then iteratively reduces the potential width as we move up in rows to count valid submatrices.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(m * n^2), Space Complexity: O(m*n).

Try this approach in the editor →

Approach 3: Enumeration + Prefix Sum

We can enumerate the bottom-right corner (i, j) of the matrix, and then enumerate the first row k upwards. The width of the matrix with (i, j) as the bottom-right corner in each row is min_{k leq i} g[k][j], where g[k][j] represents the width of the matrix with (k, j) as the bottom-right corner in the k-th row.

Therefore, we can preprocess a 2D array g[i][j], where g[i][j] represents the number of consecutive 1s from the j-th column to the left in the i-th row.

The time complexity is O(m^2 times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the matrix, respectively.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Histogram Approach

Time Complexity: O(m * n^2), where m is the number of rows and n is the number of columns. Space Complexity: O(n) for the height and stack arrays.

Dynamic Programming Approach

Time Complexity: O(m * n^2), Space Complexity: O(m*n).

Enumeration + Prefix Sum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Upward ExpansionO(m * n^2)O(n)Good first solution in interviews. Easy to reason about using width tracking.
Histogram + Monotonic StackO(m * n)O(n)Optimal solution. Best for large matrices and expected in strong interview answers.

Video Solution

Leetcode 1504. Count Submatrices With All Ones • Fraz • 35,078 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Submatrices With All Ones easy or hard?
Count Submatrices With All Ones is classified as a Medium problem on LeetCode. The brute force idea is simple, but recognizing the histogram transformation and applying a monotonic stack requires solid experience with matrix and stack-based algorithms.
Count Submatrices With All Ones Python/Java solution
Python and Java implementations typically build a height array for each row and apply a monotonic stack to compute rectangle counts. Both implementations run in O(m * n) time and require only O(n) additional space.
How to solve Count Submatrices With All Ones in O(n)?
Treat every row as the base of a histogram where each column stores the height of consecutive ones. Use a monotonic increasing stack to count how many rectangles end at each column efficiently. Processing each row this way leads to an overall O(m * n) algorithm.
What is the best approach for Count Submatrices With All Ones?
The optimal approach converts each row into a histogram of consecutive vertical ones and then counts rectangles using a monotonic stack. This method processes each column once per row and achieves O(m * n) time complexity with O(n) extra space.
Is Count Submatrices With All Ones asked at Google/Amazon/Meta?
Matrix counting problems with histogram or monotonic stack patterns appear frequently in interviews at companies like Google, Amazon, and Meta. Variations of this problem are commonly used to test understanding of stacks, dynamic programming, and 2D array transformations.
What data structure is used in Count Submatrices With All Ones?
The optimal solution relies on a monotonic stack along with an array representing histogram heights. The stack maintains increasing column heights so rectangles can be counted efficiently without rechecking previous columns.
What is the time complexity of Count Submatrices With All Ones?
The optimal histogram + monotonic stack solution runs in O(m * n) time, where m is the number of rows and n is the number of columns. Each element is pushed and popped from the stack at most once per row. A simpler dynamic programming approach runs in O(m * n^2).

Ready to solve this problem?

Practice Count Submatrices With All Ones with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Submatrices With Equal Frequency of X and Y