Scale Engineer

Count Submatrices With All Ones

Med
#1387Time: O(m³ * n³)Space: O(1)
Patterns
Dynamic Programming
Data structures
ArrayStackMatrixMonotonic Stack

Prompt

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:

  • 1 <= m, n <= 150
  • mat[i][j] is either 0 or 1.

Approaches

4 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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

Complexity

Time

O(m³ * n³)

Space

O(1)

Trade-offs

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.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem