# 1504. Count Submatrices With All Ones

## Approach 1: Naive

• Time: $O(m^2n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { public: int numSubmat(vector>& mat) { const int m = mat.size(); const int n = mat[0].size(); int ans = 0; for (int baseRow = 0; baseRow < m; ++baseRow) { vector 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& row) { int ans = 0; int length = 0; for (const int a : row) { length = a == 0 ? 0 : length + 1; ans += length; } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 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 ans = 0; int length = 0; for (final int a : row) { length = a == 0 ? 0 : length + 1; ans += length; } return ans; } } 

## Approach 2: Stack

• Time: $O(mn)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution { public: int numSubmat(vector>& mat) { const int m = mat.size(); const int n = mat[0].size(); int ans = 0; vector hist(n); for (const vector& row : mat) { for (int i = 0; i < row.size(); ++i) hist[i] = row[i] == 0 ? 0 : hist[i] + 1; ans += count(hist); } return ans; } private: int count(const vector& A) { // submatrices[i] := # of submatrices w/ column i as the right border vector submatrices(A.size()); stack stack; for (int i = 0; i < A.size(); ++i) { while (!stack.empty() && A[stack.top()] >= A[i]) stack.pop(); if (!stack.empty()) { const int prevIndex = stack.top(); submatrices[i] = submatrices[prevIndex] + A[i] * (i - prevIndex); } else { submatrices[i] = A[i] * (i + 1); } stack.push(i); } return accumulate(begin(submatrices), end(submatrices), 0); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public int numSubmat(int[][] mat) { final int m = mat.length; final int n = mat[0].length; int ans = 0; int[] hist = new int[n]; for (int[] row : mat) { for (int i = 0; i < row.length; ++i) hist[i] = row[i] == 0 ? 0 : hist[i] + 1; ans += count(hist); } return ans; } private int count(int[] A) { // submatrices[i] := # of submatrices w/ column i as the right border int[] submatrices = new int[A.length]; Deque stack = new ArrayDeque<>(); for (int i = 0; i < A.length; ++i) { while (!stack.isEmpty() && A[stack.peek()] >= A[i]) stack.pop(); if (!stack.isEmpty()) { final int prevIndex = stack.peek(); submatrices[i] = submatrices[prevIndex] + A[i] * (i - prevIndex); } else { submatrices[i] = A[i] * (i + 1); } stack.push(i); } return Arrays.stream(submatrices).sum(); } }