Count Submatrices With All Ones | Leetcode 1504

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();

        int count = 0, curr_count;
        vector<int> histogram(n);
        for(int i=0;i<m;++i){
            // Update the current row to histogram
            for(int j=0;j<n;++j){
                if(mat[i][j]==1)    histogram[j]+=1;
                else                histogram[j]=0;
            }
            stack<vector<int>> st;  //{height,index,prev_count}
            st.push({-1,-1,0});

            for(int j=0;j<n;++j){
                while(st.top()[0]>=histogram[j])
                        st.pop();

                curr_count = histogram[j] * (j-st.top()[1]) + st.top()[2];
                st.push({histogram[j],j,curr_count});
                count += curr_count;
            }
        }
        return count;
    }
};
/*
//Java

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

        int[] histogram = new int[n];
        int count = 0;

        for (int i = 0; i < m; ++i) {
            // update histogram for row i
            for (int j = 0; j < n; ++j) {
                histogram[j] = (mat[i][j] == 1) ? histogram[j] + 1 : 0;
            }

            // stack of int[]{height, index, prevCount}
            Deque<int[]> st = new ArrayDeque<>();
            st.push(new int[]{-1, -1, 0}); // sentinel

            int currCount = 0;
            for (int j = 0; j < n; ++j) {
                while (st.peek()[0] >= histogram[j]) {
                    st.pop();
                }
                int[] top = st.peek();
                currCount = histogram[j] * (j - top[1]) + top[2];
                st.push(new int[]{histogram[j], j, currCount});
                count += currCount;
            }
        }

        return count;
    }
}

#Python
from typing import List

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])
        histogram = [0] * n
        count = 0

        for i in range(m):
            # update histogram for row i
            for j in range(n):
                histogram[j] = histogram[j] + 1 if mat[i][j] == 1 else 0

            # stack of tuples (height, index, prev_count); start with sentinel
            stack = [(-1, -1, 0)]
            for j in range(n):
                while stack and stack[-1][0] >= histogram[j]:
                    stack.pop()
                prev_h, prev_idx, prev_count = stack[-1]
                curr_count = histogram[j] * (j - prev_idx) + prev_count
                stack.append((histogram[j], j, curr_count))
                count += curr_count

        return count

*/