-
Notifications
You must be signed in to change notification settings - Fork 118
/
1504. Count Submatrices With All Ones.cpp
205 lines (180 loc) · 6.33 KB
/
1504. Count Submatrices With All Ones.cpp
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
//TLE
//67 / 72 test cases passed.
//time: O(m^2 * n^2)
class Solution {
public:
int numSubmat(vector<vector<int>>& mat) {
int m = mat.size();
if(m == 0) return 0;
int n = mat[0].size();
if(n == 0) return 0;
/*
padding a row and a column ahead
so submatrixSum[i][j] corresponds to matrix[i-1][j-1]
*/
vector<vector<int>> sms(m+1, vector(n+1, 0)); //submatrixSum
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
/*
submatrix down to prev row + submatrix right to prev column - submatrix to its left-top
plus
current element
*/
sms[i][j] += sms[i-1][j] + sms[i][j-1] - sms[i-1][j-1] + mat[i-1][j-1];
// cout << sms[i][j] << " ";
}
// cout << endl;
}
int ans = 0;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
//the length of the edge of the square
for(int li = 1; li <= i; li++){
for(int lj = 1; lj <= j; lj++){
/*
use sms[i][j] - sms[i-len][j] - sms[i][j-len] + sms[i-len][j-len] to
calculate the sum of matrix[i-len...i-1, j-len...j-1]
*/
if(sms[i][j] - sms[i-li][j] - sms[i][j-lj] + sms[i-li][j-lj] == li * lj){
// cout << "(" << i << ", " << j << "), length: " << len << endl;
ans++;
}
}
}
}
}
return ans;
}
};
//compress submatrix into an array
//https://leetcode.com/problems/count-submatrices-with-all-ones/discuss/720265/Java-Detailed-Explanation-From-O(MNM)-to-O(MN)-by-using-Stack
//Runtime: 132 ms, faster than 39.02% of C++ online submissions for Count Submatrices With All Ones.
//Memory Usage: 14.2 MB, less than 100.00% of C++ online submissions for Count Submatrices With All Ones.
//time: O(m^2 * n)
class Solution {
public:
int numSubarr(vector<int>& arr){
int n = arr.size();
int len = 0, count = 0;
for(int i = 0; i < n; ++i){
/*
len: the count of all one subarray
ending at "i"
*/
len = (arr[i] == 0) ? 0 : len+1;
/*
count is the sum of subarrays
ending at i=0~n-1
*/
count += len;
}
return count;
};
int numSubmat(vector<vector<int>>& mat) {
int m = mat.size();
if(m == 0) return 0;
int n = mat[0].size();
if(n == 0) return 0;
int count = 0;
for(int up = 0; up < m; ++up){
/*
h is the compressed matrix mat[up~down, 0~n-1]
*/
vector<int> h(n, 1);
for(int down = up; down < m; ++down){
/*
extend the submatrix by adding the row "down"
and add its info into the compressed matrix "h"
*/
for(int i = 0; i < n; ++i){
h[i] &= mat[down][i];
}
/*
sum of submatrices (up, down) = (0,0) to (m-1, m-1)
*/
count += numSubarr(h);
// cout << "[" << up << ", " << down << "]: " << numSubarr(h) << endl;
}
}
return count;
}
};
//monotonic stack
//Runtime: 76 ms, faster than 89.47% of C++ online submissions for Count Submatrices With All Ones.
//Memory Usage: 16.3 MB, less than 100.00% of C++ online submissions for Count Submatrices With All Ones.
//https://leetcode.com/problems/count-submatrices-with-all-ones/discuss/720265/Java-Detailed-Explanation-From-O(MNM)-to-O(MN)-by-using-Stack
//time: O(m*n)
class Solution {
public:
int helper(vector<int>& h){
/*
counts[j]: count of submatrix ending at column j
*/
vector<int> counts(h.size());
/*
monotonic stack,
top element is the largest
*/
stack<int> stk;
for(int j = 0; j < h.size(); ++j){
/*
we want to find the former nearset column
which is lower
*/
while(!stk.empty() && h[stk.top()] >= h[j]){
stk.pop();
}
if(!stk.empty()){
int preIndex = stk.top();
/*
valid height range: [1,h[j]]
valid width range:[preIndex+1,j]
add count of submatrices ending at
column preIndex: counts[preIndex]??
*/
/*
why not adding the submatrices formed by
even former, even shorter columns??
*/
counts[j] = h[j] * (j - preIndex) + counts[preIndex];
}else{
/*
all previous columns' are
at least taller as current column,
so the submatrices can start at one of [0,j]
valid height range: [1,h[j]]
valid width range: [0,j]
so total we could have h[j] * (j+1) submatrices
ending at j
*/
counts[j] = h[j] * (j+1);
}
/*
current index j is pushed into stack,
it's used later as previous index
*/
stk.push(j);
}
return accumulate(counts.begin(), counts.end(), 0);
};
int numSubmat(vector<vector<int>>& mat) {
int m = mat.size();
if(m == 0) return 0;
int n = mat[0].size();
if(n == 0) return 0;
int count = 0;
vector<int> h(n, 0);
for(int i = 0; i < m; ++i){
//construct h
for(int j = 0; j < n; ++j){
/*
h[j]: height of continuous ones in column j,
its bottom is row i
*/
h[j] = (mat[i][j] == 0) ? 0 : h[j]+1;
}
count += helper(h);
}
return count;
}
};