1504. Count Submatrices With All Ones LeetCode Solution

Last updated: February 24, 2025

In this guide, you will get 1504. Count Submatrices With All Ones LeetCode Solution with the best time and space complexity. The solution to Count Submatrices With All Ones problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Submatrices With All Ones solution in C++
Count Submatrices With All Ones solution in Java
Count Submatrices With All Ones solution in Python
Additional Resources

1504. Count Submatrices With All Ones LeetCode Solution image

Problem Statement of Count Submatrices With All Ones

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 1×1.
There are 2 rectangles of side 1×2.
There are 3 rectangles of side 2×1.
There is 1 rectangle of side 2×2.
There is 1 rectangle of side 3×1.
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 1×1.
There are 5 rectangles of side 1×2.
There are 2 rectangles of side 1×3.
There are 4 rectangles of side 2×1.
There are 2 rectangles of side 2×2.
There are 2 rectangles of side 3×1.
There is 1 rectangle of side 3×2.
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.

Complexity Analysis

Time Complexity: O(m^2n)
Space Complexity: O(1)

1504. Count Submatrices With All Ones LeetCode Solution in C++

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

    for (int baseRow = 0; baseRow < m; ++baseRow) {
      vector<int> row(n, 1);
      for (int i = baseRow; i < m; ++i) {
        for (int j = 0; j < n; ++j)
          row[j] &= mat[i][j];
        ans += count(row);
      }
    }

    return ans;
  }

 private:
  int count(vector<int>& row) {
    int res = 0;
    int length = 0;
    for (const int num : row) {
      length = num == 0 ? 0 : length + 1;
      res += length;
    }
    return res;
  }
};
/* code provided by PROGIEZ */

1504. Count Submatrices With All Ones LeetCode Solution in Java

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

    for (int baseRow = 0; baseRow < m; ++baseRow) {
      int[] row = new int[n];
      Arrays.fill(row, 1);
      for (int i = baseRow; i < m; ++i) {
        for (int j = 0; j < n; ++j)
          row[j] &= mat[i][j];
        ans += count(row);
      }
    }

    return ans;
  }

  private int count(int[] row) {
    int res = 0;
    int length = 0;
    for (final int num : row) {
      length = num == 0 ? 0 : length + 1;
      res += length;
    }
    return res;
  }
}
// code provided by PROGIEZ

1504. Count Submatrices With All Ones LeetCode Solution in Python

class Solution:
  def numSubmat(self, mat: list[list[int]]) -> int:
    m = len(mat)
    n = len(mat[0])
    ans = 0

    for baseRow in range(m):
      row = [1] * n
      for i in range(baseRow, m):
        for j in range(n):
          row[j] &= mat[i][j]
        ans += self._count(row)

    return ans

  def _count(self, row: list[int]) -> int:
    res = 0
    length = 0
    for num in row:
      length = 0 if num == 0 else length + 1
      res += length
    return res
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents