> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/count-submatrices-with-all-ones.md).

# Count Submatrices With All Ones

Given a `rows * columns` matrix `mat` of ones and zeros, return how many **submatrices** 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.
```

**Example 3:**

```
Input: mat = [[1,1,1,1,1,1]]
Output: 21
```

**Example 4:**

```
Input: mat = [[1,0,1],[0,1,0],[1,0,1]]
Output: 5
```

**Constraints:**

* `1 <= rows <= 150`
* `1 <= columns <= 150`
* `0 <= mat[i][j] <= 1`

```java
import java.util.*;

class Solution {
    public int numSubmat(int[][] mat) {
        int M = mat.length, N = mat[0].length;
        int count = 0;
        int[] hist = new int[N];
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j)
                hist[j] = (mat[i][j] == 0 ? 0 : hist[j] + 1);
            count += helper(hist);
        }
        return count;
    }

    private int helper(int[] hist) {
        // Actually sum[i] means the number of submatrices with the column "i" as the
        // right border, which is exactly equal to the rectangle area.
        int[] sum = new int[hist.length];
        Deque<Integer> st = new LinkedList<>();
        for (int i = 0; i < hist.length; ++i) {
            // Maintaining strictly decreasing stack
            while (!st.isEmpty() && hist[st.peek()] >= hist[i])
                st.pop();
            // If stack is not empty, meaning: there is a shorter column which breaks our
            // road. Now, the number of metrics can form is sum[i] += A[i] * (i - preIndex).
            // And plus, we can form a extend submetrics with that previous shorter column
            // sum[preIndex].
            if (!st.isEmpty()) {
                int preIndex = st.peek();
                sum[i] = sum[preIndex];
                sum[i] += hist[i] * (i - preIndex);
            }
            // If stack is empty, meaning: all previous columns has more/equal ones than
            // current column. So, the number of metrics can form is simply A[i] * (i + 1);
            // (0-index)
            else
                sum[i] = hist[i] * (i + 1);
            st.push(i);
        }
        int count = 0;
        for (int s : sum)
            count += s;
        return count;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/count-submatrices-with-all-ones.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.