I like to read this solution as a small machine: keep the useful information, throw away the noise. For 699. Falling Squares, the solution in this repository is mainly a binary search solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. 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: binary search, two pointers, sliding window, greedy.
The notes already sitting in the source point us in the right direction:
- https://leetcode.com/problems/falling-squares/discuss/108770/O(nlogn)-C%2B%2B-Segment-Tree
- https://leetcode.com/articles/a-recursive-approach-to-segment-trees-range-sum-queries-lazy-propagation/
- Approach 4: Segment Tree with Lazy Propagation
- time: O(NlogN), space: O(N)
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are print, push_up, push_down, update, query.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
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(NlogN), space: O(N)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//https://leetcode.com/problems/falling-squares/discuss/108770/O(nlogn)-C%2B%2B-Segment-Tree
02//https://leetcode.com/articles/a-recursive-approach-to-segment-trees-range-sum-queries-lazy-propagation/
03//Approach 4: Segment Tree with Lazy Propagation
04//time: O(NlogN), space: O(N)
05//Runtime: 68 ms, faster than 34.15% of C++ online submissions for Falling Squares.
06//Memory Usage: 13.1 MB, less than 100.00% of C++ online submissions for Falling Squares.
07class LazySegTree {
08public:
09 int n;
10 vector<int> tree, lazy;
11
12 //tree's index start from 0
13
14 LazySegTree(int n){
15 this->n = n;
16 tree = vector<int>(n*4, 0);
17 lazy = vector<int>(n*4, 0);
18 };
19
20 void print(){
21 for(int e : tree){
22 cout << e << " ";
23 }
24 cout << endl;
25
26 for(int e : lazy){
27 cout << e << " ";
28 }
29 cout << endl;
30 }
31
32 void push_up(int treeIndex) {
33 //update i by its children
34 tree[treeIndex] = max(tree[treeIndex*2+1], tree[treeIndex*2+2]);
35 }
36
37 void push_down(int treeIndex) {
38 //remove laziness of i
39 if (lazy[treeIndex]) {
40 lazy[treeIndex*2+1] = lazy[treeIndex*2+2] = lazy[treeIndex];
41 tree[treeIndex*2+1] = tree[treeIndex*2+2] = lazy[treeIndex];
42 lazy[treeIndex] = 0;
43 }
44 }
45
46 void update(int treeIndex, int l, int r, int ql, int qr, int val) {
47 //looking at [l,r], which totally falls in [ql,qr]
48 if (ql <= l && r <= qr) {
49 tree[treeIndex] = val;
50 //don't need to remove laziness first?
51 lazy[treeIndex] = val;
52 return;
53 }
54 push_down(treeIndex);
55 int mid = l + (r-l)/2;
56 if (ql < mid) update(treeIndex*2+1, l, mid, ql, qr, val);
57 if (qr > mid) update(treeIndex*2+2, mid, r, ql, qr, val);
58 push_up(treeIndex);
59 }
60
61 int query(int treeIndex, int l, int r, int ql, int qr) {
62 //looking at [l,r], which totally falls in [ql,qr]
63 if (ql <= l && r <= qr) return tree[treeIndex];
64 int res = 0;
65
66 //remove laziness
67 push_down(treeIndex);
68
69 int mid = l + (r-l)/2;
70 /*
71 ql...mid...qr or ql...qr...mid
72 if query range has intersection with left subtree,
73 then recursively query in left subtree
74 */
75 if (ql < mid) res = max(res, query(treeIndex*2+1, l, mid, ql, min(mid,qr)));
76 /*
77 ql...mid...qr or mid...ql...qr
78 if query range has intersection with right subtree,
79 then recursively query in right subtree
80 */
81 if (qr > mid) res = max(res, query(treeIndex*2+2, mid, r, max(mid,ql), qr));
82
83 return res;
84 }
85};
86
87class Solution {
88public:
89 vector<int> fallingSquares(vector<vector<int>>& positions) {
90 set<int> coords;
91 vector<int> sortedCoords;
92 vector<int> res;
93 map<int, int> index;
94
95 for (auto& pos : positions) {
96 coords.insert(pos[0]);
97 coords.insert(pos[0]+pos[1]);
98 }
99
100 sortedCoords = vector<int>(coords.begin(), coords.end());
101 sort(sortedCoords.begin(), sortedCoords.end());
102
103 // cout << "sorted: ";
104 for(int i = 0; i < sortedCoords.size(); i++){
105 index[sortedCoords[i]] = i;
106 // cout << sortedCoords[i] << " ";
107 }
108 // cout << endl;
109
110 LazySegTree tree((int)sortedCoords.size());
111
112 for (auto& pos : positions) {
113 int l = index[pos[0]];
114 int r = index[pos[0]+pos[1]];
115 // cout << "[" << l << ", " << r << "]" << endl;
116 int maxh = tree.query(0, 0, tree.n-1, l, r);
117 // tree.print();
118 tree.update(0, 0, tree.n-1, l, r, maxh+pos[1]);
119 // tree.print();
120 res.push_back(tree.query(0, 0, tree.n-1, 0, tree.n-1));
121 }
122
123 return res;
124 }
125};
126
127//Approach 1: Offline Propagation
128//Runtime: 84 ms, faster than 18.90% of C++ online submissions for Falling Squares.
129//Memory Usage: 9 MB, less than 100.00% of C++ online submissions for Falling Squares.
130//time: O(N^2), space: O(N)
131class Solution {
132public:
133 vector<int> fallingSquares(vector<vector<int>>& positions) {
134 vector<int> qans(positions.size());
135 for(int i = 0; i < positions.size(); i++){
136 int left = positions[i][0];
137 int height = positions[i][1];
138 int right = left + height -1;
139 qans[i] += height;
140
141 // for(int j = 0; j < i; j++){ //why not?
142 for(int j = i+1; j < positions.size(); j++){
143 int left2 = positions[j][0];
144 int height2 = positions[j][1];
145 int right2 = left2 + height2 -1;
146 if(left2 <= right && right2 >= left){
147 //the two squares have intersection
148 qans[j] = max(qans[j], qans[i]);
149 }
150 }
151 }
152
153 vector<int> ans;
154 int cur = -1;
155 for(int h : qans){
156 cur = max(cur, h);
157 ans.push_back(cur);
158 }
159
160 return ans;
161 }
162};
163
164//Approach 2: Brute Force with Coordinate Compression
165//time: O(N^2), space: O(N)
166//Runtime: 100 ms, faster than 15.66% of C++ online submissions for Falling Squares.
167//Memory Usage: 12.3 MB, less than 100.00% of C++ online submissions for Falling Squares.
168class Solution {
169public:
170 vector<int> heights;
171
172 int query(int L, int R){
173 return *max_element(heights.begin()+L, heights.begin()+R+1);
174 }
175
176 void update(int L, int R, int h){
177 for(int i = L; i <= R; i++){
178 // heights[i] = max(h, heights[i]);
179 heights[i] = h;
180 }
181 }
182
183 vector<int> fallingSquares(vector<vector<int>>& positions) {
184 set<int> coords;
185 for(vector<int>& pos : positions){
186 coords.insert(pos[0]);
187 coords.insert(pos[0]+pos[1]-1);
188 }
189
190 vector<int> sortedCoords(coords.begin(), coords.end());
191 sort(sortedCoords.begin(), sortedCoords.end());
192
193 map<int, int> index;
194 for(int i = 0; i < sortedCoords.size(); i++){
195 index[sortedCoords[i]] = i;
196 }
197
198 heights =vector<int>(sortedCoords.size());
199 int best = 0;
200 vector<int> ans;
201
202 for(vector<int>& pos : positions){
203 int L = index[pos[0]];
204 int R = index[pos[0]+pos[1]-1];
205 int h = query(L, R) + pos[1];
206 update(L, R, h);
207 best = max(best, h);
208 ans.push_back(best);
209 }
210
211 return ans;
212 }
213};
214
215//Approach 3: Block (Square Root) Decomposition
216//time: O(Nsqrt(N)), space: O(N)
217//Runtime: 60 ms, faster than 45.78% of C++ online submissions for Falling Squares.
218//Memory Usage: 12.6 MB, less than 100.00% of C++ online submissions for Falling Squares.
219class Solution {
220public:
221 vector<int> heights;
222 vector<int> blocks;
223 vector<int> blocks_read;
224 int B;
225
226 int query(int left, int right){
227 int ans = 0;
228
229 //left is not at the beginning of a block
230 while(left % B > 0 && left <= right){
231 ans = max(ans, heights[left]);
232 //?
233 ans = max(ans, blocks[left/B]);
234 left++;
235 }
236
237 //right is not at the end of a block
238 while(right % B != B-1 && left <= right){
239 ans = max(ans, heights[right]);
240 ans = max(ans, blocks[right/B]);
241 right--;
242 }
243
244 //now left is at the beginning and right is at the end of block
245 while(left <= right){
246 ans = max(ans, blocks[left/B]);
247 //?
248 ans = max(ans, blocks_read[left/B]);
249 left += B;
250 }
251
252 return ans;
253 }
254
255 void update(int left, int right, int h){
256 while(left % B > 0 && left <= right){
257 heights[left] = max(heights[left], h);
258 blocks_read[left/B] = max(blocks_read[left/B], h);
259 left++;
260 }
261 while(right % B != B-1 && left <= right){
262 heights[right] = max(heights[right], h);
263 blocks_read[right/B] = max(blocks_read[right/B], h);
264 right--;
265 }
266 while(left <= right){
267 blocks[left/B] = max(blocks[left/B], h);
268 left+=B;
269 }
270 }
271
272 vector<int> fallingSquares(vector<vector<int>>& positions) {
273 set<int> coords;
274 for(vector<int>& pos : positions){
275 coords.insert(pos[0]);
276 coords.insert(pos[0]+pos[1]-1);
277 }
278
279 vector<int> sortedCoords(coords.begin(), coords.end());
280 sort(sortedCoords.begin(), sortedCoords.end());
281
282 map<int, int> index;
283 for(int i = 0; i < sortedCoords.size(); i++){
284 index[sortedCoords[i]] = i;
285 }
286
287 heights = vector<int>(sortedCoords.size());
288 B = (int)sqrt(sortedCoords.size());
289 blocks = vector<int>(B+2, 0);
290 blocks_read = vector<int>(B+2, 0);
291
292 int best = 0;
293 vector<int> ans;
294
295 for(vector<int>& pos : positions){
296 int L = index[pos[0]];
297 int R = index[pos[0]+pos[1]-1];
298 int h = query(L, R) + pos[1];
299 update(L, R, h);
300 best = max(best, h);
301 ans.push_back(best);
302 }
303
304 return ans;
305 }
306};Cost
Complexity
Time
O(NlogN), space: O(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.