1504

1504. Count Submatrices With All Ones (Medium)

Given a rows * columns matrix mat of ones and zeros, return how many submatrices 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.

Example 3:

Input: mat = [[1,1,1,1,1,1]]
Output: 21

Example 4:

Input: mat = [[1,0,1],[0,1,0],[1,0,1]]
Output: 5

 

Constraints:

• 1 <= rows <= 150
• 1 <= columns <= 150
• 0 <= mat[i][j] <= 1

Related Topics:
Dynamic Programming

Solution 1.

For the ith row, regard the cells with ones in and above this row as histograms.

H[j] is the height of the histogram at column j.

For each 0 <= j < N, count how many all-one rectangles are there with A[i][j] being the bottom-right element. h is the height of the rectangle and k is the index of the left edge column.

// OJ: https://leetcode.com/problems/count-submatrices-with-all-ones/
// Author: github.com/lzl124631x
// Time: O(M * N^2)
// Space: O(N)
class Solution {
public:
    int numSubmat(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size(), ans = 0;
        vector<int> H(N);
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) H[j] = A[i][j] ? 1 + H[j] : 0;
            for (int j = 0; j < N; ++j) {
                int h = H[j];
                for (int k = j; k >= 0; --k) {
                    h = min(h, H[k]);
                    ans += h;
                }
            }
        }
        return ans;
    }
};

Solution 2. Monostack

// OJ: https://leetcode.com/problems/count-submatrices-with-all-ones/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(N)
class Solution {
public:
    int numSubmat(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size(), ans = 0;
        vector<int> H(N);
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) H[j] = A[i][j] ? 1 + H[j] : 0;
            stack<pair<int, int>> s; // index, height
            int cnt = 0;
            for (int j = 0; j < N; ++j) {
                int prev = j;
                while (s.size() && s.top().second > H[j]) {
                    cnt -= (prev - s.top().first) * (s.top().second - H[j]);
                    prev = s.top().first;
                    s.pop();
                }
                if (s.empty() || s.top().second < H[j]) s.emplace(prev, H[j]);
                cnt += s.top().second;
                ans += cnt;
            }
        }
        return ans;
    }
};

Another variation.

// OJ: https://leetcode.com/problems/count-submatrices-with-all-ones/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(N)
class Solution {
public:
    int numSubmat(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size(), ans = 0;
        vector<int> H(N);
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) H[j] = A[i][j] ? 1 + H[j] : 0;
            vector<int> sum(N);
            stack<int> s;
            for (int j = 0; j < N; ++j) {
                while (s.size() && H[s.top()] >= H[j]) s.pop();
                sum[j] = (s.size() ? sum[s.top()] : 0) + (j - (s.size() ? s.top() : -1)) * H[j];
                ans += sum[j];
                s.push(j);
            }
        }
        return ans;
    }
};