← All problems

1504. Count Submatrices with All Ones

MediumOpen on LeetCodeProblem statement

Problem Statement

1504. Count Submatrices With All Ones

Medium

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:

Java

Source file
class Solution {
    public int numSubmat(int[][] mat) {
        int m = mat.length, n = mat[0].length, res = 0;
        int[] ht = new int[n];
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++)
                ht[j] = mat[i][j] == 0 ? 0 : ht[j] + 1;
            Stack<int[]> monoStk = new Stack<>();
            monoStk.push(new int[]{-1, 0});  // col num, cur dp val
            for(int j=0; j<n; j++){
                while(monoStk.peek()[0]>=0 && ht[monoStk.peek()[0]]>=ht[j])
                    monoStk.pop();  // curr ht is  the limiting constraint so remove others that are deeper
                int[] top = monoStk.peek();
                int shorterJ = top[0], curr = top[1] + (j - shorterJ) * ht[j];
                monoStk.push(new int[]{j, curr});
                res += curr;
            }
        }
        return res;
    }
}