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

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;
    }
}