# Count Submatrices With All Ones
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-submatrices-with-all-ones)
Canonical: https://scaleengineer.com/dsa/problems/count-submatrices-with-all-ones
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Stack, Matrix, Monotonic Stack
---
## Problem
Given an `m x n` binary matrix `mat`, _return the number of **submatrices** that have all ones_.

**Example 1:**

![](https://assets.glich.co/dsa/count-submatrices-with-all-ones/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/count-submatrices-with-all-ones/image1.jpg) 

**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`.

# Approaches
## Brute Force Enumeration
The most straightforward approach is to generate every possible submatrix and check if it contains all ones. A submatrix can be defined by its top-left corner `(r1, c1)` and its bottom-right corner `(r2, c2)`. We can use four nested loops to iterate through all possible combinations of these corners. For each submatrix, we then perform another nested iteration to verify that all its elements are `1`. If they are, we increment a counter.
**Time:** O(m³ * n³) · **Space:** O(1)
**Pros:** Simple to conceptualize and implement.; Requires no extra space.
**Cons:** Extremely inefficient due to six nested loops in total.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
This method exhaustively checks every single submatrix within the given matrix `mat`. The process is as follows:

- We iterate through each possible starting row `r1` from `0` to `m-1`.
- For each `r1`, we iterate through each possible starting column `c1` from `0` to `n-1`.
- This pair `(r1, c1)` defines the top-left corner of a potential submatrix.
- Then, for each top-left corner, we iterate through all possible ending rows `r2` from `r1` to `m-1`.
- And for each `r2`, we iterate through all possible ending columns `c2` from `c1` to `n-1`.
- This `(r2, c2)` pair defines the bottom-right corner.
- Once a submatrix is defined, we must verify if it's composed entirely of ones. A helper function can do this by iterating from row `r1` to `r2` and column `c1` to `c2`. If a `0` is found, the submatrix is invalid. If the entire submatrix is traversed without finding a `0`, it's a valid all-ones submatrix, and we increment our total count.

```java
class Solution {
    public int numSubmat(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int count = 0;
        for (int r1 = 0; r1 < m; r1++) {
            for (int c1 = 0; c1 < n; c1++) {
                for (int r2 = r1; r2 < m; r2++) {
                    for (int c2 = c1; c2 < n; c2++) {
                        if (isAllOnes(mat, r1, c1, r2, c2)) {
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }

    private boolean isAllOnes(int[][] mat, int r1, int c1, int r2, int c2) {
        for (int i = r1; i <= r2; i++) {
            for (int j = c1; j <= c2; j++) {
                if (mat[i][j] == 0) {
                    return false;
                }
            }
        }
        return true;
    }
}
```
### Algorithm
1. Initialize a counter `count` to 0.
2. Use four nested loops to iterate through all possible top-left `(r1, c1)` and bottom-right `(r2, c2)` corners of submatrices.
3. For each submatrix defined by these corners, create a helper function `isAllOnes`.
4. The `isAllOnes` function iterates through every cell from `(r1, c1)` to `(r2, c2)`.
5. If it finds any cell with a value of `0`, it immediately returns `false`.
6. If the loops complete without finding any `0`, it returns `true`.
7. If `isAllOnes` returns `true`, increment the `count`.
8. After all possible submatrices are checked, return the final `count`.

## Brute Force with 2D Prefix Sum
The brute-force approach is slow because the check for an all-ones submatrix takes `O(m*n)` time. We can optimize this check to `O(1)` using a 2D prefix sum array. We first precompute a matrix where each cell `(i, j)` stores the sum of all elements in the rectangle from `(0, 0)` to `(i, j)`. With this, the sum of any submatrix can be found in constant time. We then iterate through all possible submatrices, and if a submatrix's sum equals its area, we count it.
**Time:** O(m² * n²) · **Space:** O(m * n) for the prefix sum matrix.
**Pros:** Much faster than the pure brute-force approach.; Introduces the useful concept of prefix sums.
**Cons:** The time complexity is still too high for the given constraints.; Requires O(m*n) extra space for the prefix sum matrix.
### Explanation
This approach improves upon the pure brute-force method by optimizing the verification step. The key idea is to pre-calculate sums of rectangular regions of the matrix.

- **Precomputation:** We create a `prefixSum` matrix of size `(m+1) x (n+1)`. `prefixSum[i][j]` will store the sum of elements in `mat` from `(0,0)` to `(i-1, j-1)`. This can be computed in `O(m*n)` time.
- **Verification:** Once the `prefixSum` matrix is built, the sum of any submatrix defined by `(r1, c1)` and `(r2, c2)` can be calculated in `O(1)` time. The sum is `prefixSum[r2+1][c2+1] - prefixSum[r1][c2+1] - prefixSum[r2+1][c1] + prefixSum[r1][c1]`.
- **Counting:** We still iterate through all `O(m^2 * n^2)` possible submatrices. For each one, we calculate its sum and its area. If `sum == area`, it must be an all-ones submatrix, so we increment our counter.

While the check is now `O(1)`, the overall complexity is dominated by iterating through all submatrices.

```java
class Solution {
    public int numSubmat(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] prefixSum = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefixSum[i + 1][j + 1] = mat[i][j] + prefixSum[i][j + 1] + prefixSum[i + 1][j] - prefixSum[i][j];
            }
        }

        int count = 0;
        for (int r1 = 0; r1 < m; r1++) {
            for (int c1 = 0; c1 < n; c1++) {
                for (int r2 = r1; r2 < m; r2++) {
                    for (int c2 = c1; c2 < n; c2++) {
                        int sum = prefixSum[r2 + 1][c2 + 1] - prefixSum[r1][c2 + 1] - prefixSum[r2 + 1][c1] + prefixSum[r1][c1];
                        int area = (r2 - r1 + 1) * (c2 - c1 + 1);
                        if (sum == area) {
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
1. Create a 2D prefix sum matrix `prefixSum` of size `(m+1) x (n+1)`.
2. Populate `prefixSum[i+1][j+1]` with the sum of all elements in the rectangle from `(0,0)` to `(i,j)` in the original matrix.
3. The formula is: `prefixSum[i+1][j+1] = mat[i][j] + prefixSum[i][j+1] + prefixSum[i+1][j] - prefixSum[i][j]`.
4. Iterate through all possible top-left `(r1, c1)` and bottom-right `(r2, c2)` corners of submatrices.
5. For each submatrix, calculate its sum in `O(1)` time using the `prefixSum` matrix.
6. Calculate the area of the submatrix: `area = (r2 - r1 + 1) * (c2 - c1 + 1)`.
7. If the sum equals the area, it means the submatrix is composed of all ones. Increment the total count.
8. Return the total count.

## Dynamic Programming on Histograms
A more efficient approach is to re-frame the problem. Instead of considering every submatrix, we can iterate through each cell `(i, j)` and count how many all-ones submatrices have this cell as their **bottom-right corner**. 

We can process the matrix row by row. For each row `i`, we can think of it as the base of a histogram, where the height of the bar at column `j` is the number of consecutive `1`s above `mat[i][j]` (inclusive). Then, for each bar `(i, j)` in this histogram, we can find how many rectangles can be formed with `(i, j)` as the bottom-right point by looking leftwards and considering the minimum height of the bars encountered.
**Time:** O(m * n²) · **Space:** O(n) for the auxiliary height array.
**Pros:** Much more efficient than brute-force approaches.; Passes the time limits for the given constraints.; The space complexity can be optimized to O(n).
**Cons:** The triple nested loop structure suggests it might not be the most optimal solution, although it's efficient enough to pass.
### Explanation
This dynamic programming approach builds the solution row by row.

- We maintain an array `height` of size `n`, which stores the heights of consecutive `1`s for the current row, forming a histogram. 
- We iterate through each row `i` from `0` to `m-1`.
- For each row, we first update the `height` array. For each column `j`, if `mat[i][j]` is `1`, we increment `height[j]`. If it's `0`, we reset `height[j]` to `0`.
- After updating the `height` array for row `i`, we calculate the number of new submatrices that have their bottom edge on this row.
- We do this by iterating through each column `j` from `0` to `n-1`. For each `j`, we consider it as the right edge of potential rectangles. We then iterate backwards from `k = j` to `0`. In this inner loop, we keep track of the minimum height (`minHeight`) in the range `[k, j]`. The number of rectangles with bottom-right corner at `(i, j)` and bottom-left corner at `(i, k)` is equal to this `minHeight`. We add this to our total count.

This reduces the complexity significantly compared to brute-force methods.

```java
class Solution {
    public int numSubmat(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int count = 0;
        int[] height = new int[n];

        for (int i = 0; i < m; i++) {
            // Update heights for the current row's histogram
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    height[j]++;
                } else {
                    height[j] = 0;
                }
            }
            
            // Calculate submatrices ending at row i
            for (int j = 0; j < n; j++) {
                int minHeight = height[j];
                for (int k = j; k >= 0 && height[k] > 0; k--) {
                    minHeight = Math.min(minHeight, height[k]);
                    count += minHeight;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
1. Initialize `count = 0` and an auxiliary array `height` of size `n` to all zeros.
2. Iterate through each row `i` of the matrix from top to bottom.
3. For each row `i`, update the `height` array. For each column `j`, `height[j]` becomes `height[j] + 1` if `mat[i][j] == 1`, and `height[j]` is reset to `0` if `mat[i][j] == 0`. This `height` array represents a histogram of consecutive ones ending at the current row.
4. After updating `height` for row `i`, iterate through each column `j` from `0` to `n-1`.
5. For each `j`, if `height[j] > 0`, start a backward loop for `k` from `j` down to `0`.
6. In the inner loop, maintain a `minHeight` which is the minimum height in the histogram from column `k` to `j`.
7. Add this `minHeight` to the total `count`. The loop for `k` stops if `height[k]` becomes `0`.
8. After iterating through all rows, return the total `count`.

## Histogram-based DP with Monotonic Stack
This approach optimizes the `O(m*n²)` solution to `O(m*n)`. The bottleneck in the previous approach was the inner loop that iterated backward from `j` to calculate the contribution of each bar in the histogram. This calculation can be optimized. For each row's histogram, we can compute the number of rectangles ending at each column `j` in amortized `O(1)` time using a dynamic programming recurrence aided by a monotonic stack. The stack helps efficiently find the 'previous smaller element' for each bar, which is key to the DP recurrence.
**Time:** O(m * n) · **Space:** O(n) for the height array, DP array, and the stack.
**Pros:** Optimal time complexity.; Efficiently solves the problem within the given constraints.; Uses a powerful combination of DP and the monotonic stack pattern.
**Cons:** The logic, especially the DP recurrence and its connection to the monotonic stack, is more complex to derive and understand.
### Explanation
This is the most optimal solution, building upon the histogram-based approach. For each row, we compute the `height` array as before. The core optimization is in how we count the rectangles for that histogram.

Let `dp[j]` be the number of all-ones submatrices whose bottom-right corner is at `(i, j)`. We can establish a recurrence for `dp[j]` based on `dp` values of previous columns in the same row.

The recurrence is: `dp[j] = dp[p] + (j - p) * height[j]`, where `p` is the index of the first bar to the left of `j` that is strictly shorter than the bar at `j` (`height[p] < height[j]`).

- **Why this recurrence works:** The rectangles ending at `(i, j)` can be split into two groups. The first group consists of rectangles that are taller than `height[p]`. Their widths are at most `j-p`. For all these rectangles, `height[j]` is not the minimum height. The second group consists of rectangles that are shorter than or equal to `height[p]`. The number of such rectangles is exactly `dp[p]`. The number of rectangles in the first group is `(j-p) * height[j]`. Summing them gives the recurrence.

- **Monotonic Stack:** To find the index `p` (previous smaller element) for each `j` efficiently, we use a monotonic stack that stores indices of bars with increasing heights. As we iterate through `j`, we pop from the stack all indices of bars that are taller than or equal to the current bar `height[j]`. The index at the top of the stack after this process is our `p`.

This allows us to calculate the contributions for an entire row in `O(n)` time, leading to an overall `O(m*n)` solution.

```java
import java.util.Stack;

class Solution {
    public int numSubmat(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int totalCount = 0;
        int[] height = new int[n];

        for (int i = 0; i < m; i++) {
            // 1. Update heights for the current row to form a histogram
            for (int j = 0; j < n; j++) {
                height[j] = (mat[i][j] == 1) ? height[j] + 1 : 0;
            }

            // 2. Calculate submatrices for the histogram of the current row
            int[] dp = new int[n]; // dp[j] = number of submatrices with bottom-right at (i, j)
            Stack<Integer> stack = new Stack<>(); // stores indices of increasing heights

            for (int j = 0; j < n; j++) {
                while (!stack.isEmpty() && height[stack.peek()] >= height[j]) {
                    stack.pop();
                }

                int p = stack.isEmpty() ? -1 : stack.peek();
                int prev_dp = (p == -1) ? 0 : dp[p];
                dp[j] = prev_dp + (j - p) * height[j];
                
                stack.push(j);
            }
            
            // 3. Add the sum of dp array to the total count
            int rowSum = 0;
            for(int val : dp) {
                rowSum += val;
            }
            totalCount += rowSum;
        }
        return totalCount;
    }
}
```
### Algorithm
1. Initialize `totalCount = 0` and a `height` array of size `n`.
2. Iterate through each row `i` from `0` to `m-1`.
3. Update the `height` array for the current row as in the previous approach.
4. For the current row's `height` histogram, calculate the number of submatrices using a DP approach with a monotonic stack.
   a. Initialize a `dp` array of size `n` and an empty `stack` (to store indices).
   b. Iterate `j` from `0` to `n-1`:
      i. While the stack is not empty and the height of the bar at the index on top of the stack is greater than or equal to `height[j]`, pop from the stack.
      ii. Find the index `p` of the previous smaller bar. If the stack is now empty, `p = -1`. Otherwise, `p` is the index at the top of the stack.
      iii. Calculate `dp[j]`, the number of rectangles ending at column `j`, using the recurrence: `dp[j] = dp[p] + (j - p) * height[j]`. (If `p` is -1, `dp[p]` is 0).
      iv. Push the current index `j` onto the stack.
   c. Sum all values in the `dp` array and add this sum to `totalCount`.
5. Return `totalCount`.

# Solutions
### Java

```java
class Solution {
public
  int numSubmat(int[][] mat) {
    int m = mat.length, n = mat[0].length;
    int[][] g = new int[m][n];
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (mat[i][j] == 1) {
          g[i][j] = j == 0 ? 1 : 1 + g[i][j - 1];
        }
      }
    }
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        int col = 1 << 30;
        for (int k = i; k >= 0 && col > 0; --k) {
          col = Math.min(col, g[k][j]);
          ans += col;
        }
      }
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int: m, n = len(mat), len(mat[0]) g = [[0] * n for _ in range(m)] for i in range(m): for j in range(n): if mat[i][j]: g[i][j] = 1 if j == 0 else 1 + g[i][j - 1] ans = 0 for i in range(m): for j in range(n): col = inf for k in range(i, - 1, - 1): col = min(col, g[k][j]) ans += col return ans

```

### CPP

```cpp
class Solution {
public:
  int numSubmat(vector<vector<int>> &mat) {
    int m = mat.size(), n = mat[0].size();
    vector<vector<int>> g(m, vector<int>(n));
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (mat[i][j] == 1) {
          g[i][j] = j == 0 ? 1 : 1 + g[i][j - 1];
        }
      }
    }
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        int col = 1 << 30;
        for (int k = i; k >= 0 && col > 0; --k) {
          col = min(col, g[k][j]);
          ans += col;
        }
      }
    }
    return ans;
  }
};

```