The trick here is to name the state correctly, then let the implementation follow. For 1504. Count Submatrices With All Ones, the solution in this repository is mainly a two pointers solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers, stack, sliding window, bit manipulation.
The notes already sitting in the source point us in the right direction:
- TLE
- 67 / 72 test cases passed.
- time: O(m^2 * n^2)
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are numSubmat, numSubarr, h, helper, counts.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The stack stores unfinished context, which is usually the cleanest way to handle nested or monotonic structure.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(m^2 * n)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//TLE
02//67 / 72 test cases passed.
03//time: O(m^2 * n^2)
04class Solution {
05public:
06 int numSubmat(vector<vector<int>>& mat) {
07 int m = mat.size();
08 if(m == 0) return 0;
09 int n = mat[0].size();
10 if(n == 0) return 0;
11
12 /*
13 padding a row and a column ahead
14 so submatrixSum[i][j] corresponds to matrix[i-1][j-1]
15 */
16 vector<vector<int>> sms(m+1, vector(n+1, 0)); //submatrixSum
17
18 for(int i = 1; i <= m; i++){
19 for(int j = 1; j <= n; j++){
20 /*
21 submatrix down to prev row + submatrix right to prev column - submatrix to its left-top
22 plus
23 current element
24 */
25 sms[i][j] += sms[i-1][j] + sms[i][j-1] - sms[i-1][j-1] + mat[i-1][j-1];
26 // cout << sms[i][j] << " ";
27 }
28 // cout << endl;
29 }
30
31 int ans = 0;
32
33 for(int i = 1; i <= m; i++){
34 for(int j = 1; j <= n; j++){
35 //the length of the edge of the square
36 for(int li = 1; li <= i; li++){
37 for(int lj = 1; lj <= j; lj++){
38 /*
39 use sms[i][j] - sms[i-len][j] - sms[i][j-len] + sms[i-len][j-len] to
40 calculate the sum of matrix[i-len...i-1, j-len...j-1]
41 */
42 if(sms[i][j] - sms[i-li][j] - sms[i][j-lj] + sms[i-li][j-lj] == li * lj){
43 // cout << "(" << i << ", " << j << "), length: " << len << endl;
44 ans++;
45 }
46 }
47 }
48 }
49 }
50
51 return ans;
52 }
53};
54
55//compress submatrix into an array
56//https://leetcode.com/problems/count-submatrices-with-all-ones/discuss/720265/Java-Detailed-Explanation-From-O(MNM)-to-O(MN)-by-using-Stack
57//Runtime: 132 ms, faster than 39.02% of C++ online submissions for Count Submatrices With All Ones.
58//Memory Usage: 14.2 MB, less than 100.00% of C++ online submissions for Count Submatrices With All Ones.
59//time: O(m^2 * n)
60class Solution {
61public:
62 int numSubarr(vector<int>& arr){
63 int n = arr.size();
64
65 int len = 0, count = 0;
66
67 for(int i = 0; i < n; ++i){
68 /*
69 len: the count of all one subarray
70 ending at "i"
71 */
72 len = (arr[i] == 0) ? 0 : len+1;
73 /*
74 count is the sum of subarrays
75 ending at i=0~n-1
76 */
77 count += len;
78 }
79
80 return count;
81 };
82
83 int numSubmat(vector<vector<int>>& mat) {
84 int m = mat.size();
85 if(m == 0) return 0;
86 int n = mat[0].size();
87 if(n == 0) return 0;
88
89 int count = 0;
90
91 for(int up = 0; up < m; ++up){
92 /*
93 h is the compressed matrix mat[up~down, 0~n-1]
94 */
95 vector<int> h(n, 1);
96 for(int down = up; down < m; ++down){
97 /*
98 extend the submatrix by adding the row "down"
99 and add its info into the compressed matrix "h"
100 */
101 for(int i = 0; i < n; ++i){
102 h[i] &= mat[down][i];
103 }
104 /*
105 sum of submatrices (up, down) = (0,0) to (m-1, m-1)
106 */
107 count += numSubarr(h);
108 // cout << "[" << up << ", " << down << "]: " << numSubarr(h) << endl;
109 }
110 }
111
112 return count;
113 }
114};
115
116//monotonic stack
117//Runtime: 76 ms, faster than 89.47% of C++ online submissions for Count Submatrices With All Ones.
118//Memory Usage: 16.3 MB, less than 100.00% of C++ online submissions for Count Submatrices With All Ones.
119//https://leetcode.com/problems/count-submatrices-with-all-ones/discuss/720265/Java-Detailed-Explanation-From-O(MNM)-to-O(MN)-by-using-Stack
120//time: O(m*n)
121class Solution {
122public:
123 int helper(vector<int>& h){
124 /*
125 counts[j]: count of submatrix ending at column j
126 */
127 vector<int> counts(h.size());
128 /*
129 monotonic stack,
130 top element is the largest
131 */
132 stack<int> stk;
133
134 for(int j = 0; j < h.size(); ++j){
135 /*
136 we want to find the former nearset column
137 which is lower
138 */
139 while(!stk.empty() && h[stk.top()] >= h[j]){
140 stk.pop();
141 }
142
143 if(!stk.empty()){
144 int preIndex = stk.top();
145 /*
146 valid height range: [1,h[j]]
147 valid width range:［preIndex+1,j]
148
149 add count of submatrices ending at
150 column preIndex: counts[preIndex]??
151 */
152 /*
153 why not adding the submatrices formed by
154 even former, even shorter columns??
155 */
156 counts[j] = h[j] * (j - preIndex) + counts[preIndex];
157 }else{
158 /*
159 all previous columns' are
160 at least taller as current column,
161 so the submatrices can start at one of [0,j]
162
163 valid height range: [1,h[j]]
164 valid width range: [0,j]
165
166 so total we could have h[j] * (j+1) submatrices
167 ending at j
168 */
169 counts[j] = h[j] * (j+1);
170 }
171
172 /*
173 current index j is pushed into stack,
174 it's used later as previous index
175 */
176 stk.push(j);
177 }
178
179 return accumulate(counts.begin(), counts.end(), 0);
180 };
181
182 int numSubmat(vector<vector<int>>& mat) {
183 int m = mat.size();
184 if(m == 0) return 0;
185 int n = mat[0].size();
186 if(n == 0) return 0;
187
188 int count = 0;
189
190 vector<int> h(n, 0);
191 for(int i = 0; i < m; ++i){
192 //construct h
193 for(int j = 0; j < n; ++j){
194 /*
195 h[j]: height of continuous ones in column j,
196 its bottom is row i
197 */
198 h[j] = (mat[i][j] == 0) ? 0 : h[j]+1;
199 }
200 count += helper(h);
201 }
202
203 return count;
204 }
205};Cost
Complexity
Time
O(m^2 * n)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.