Count Submatrices With All Ones

MEDIUM

Description

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

Checkout 4 different approaches to solve Count Submatrices With All Ones. Click on different approaches to view the approach and algorithm in detail.

Brute Force Enumeration

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

Initialize a counter count to 0.
Use four nested loops to iterate through all possible top-left (r1, c1) and bottom-right (r2, c2) corners of submatrices.
For each submatrix defined by these corners, create a helper function isAllOnes.
The isAllOnes function iterates through every cell from (r1, c1) to (r2, c2).
If it finds any cell with a value of 0, it immediately returns false.
If the loops complete without finding any 0, it returns true.
If isAllOnes returns true, increment the count.
After all possible submatrices are checked, return the final count.

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 Analysis

Time Complexity: O(m³ * n³)Space Complexity: O(1)

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Count Submatrices With All Ones. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Count Submatrices With All Ones

Patterns:

Dynamic Programming

Data Structures:

ArrayStackMatrixMonotonic Stack