The trick here is to name the state correctly, then let the implementation follow. For 315. Count of Smaller Numbers After Self, the solution in this repository is mainly a binary search 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: binary search, two pointers, sliding window, greedy.
The notes already sitting in the source point us in the right direction:
- O(N^2)
- TLE
- 15 / 16 test cases passed.
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 countSmaller, increase, query, add, get.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- 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(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//O(N^2)
02//TLE
03//15 / 16 test cases passed.
04class Solution {
05public:
06 vector<int> countSmaller(vector<int>& nums) {
07 int n = nums.size();
08
09 vector<int> ans(n);
10
11 for(int i = 0; i < n; ++i){
12 for(int j = i+1; j < n; ++j){
13 if(nums[i] > nums[j]){
14 ++ans[i];
15 }
16 }
17 }
18
19 return ans;
20 }
21};
22
23//Segment Tree
24//TLE
25//15 / 16 test cases passed.
26class SegTree{
27public:
28 vector<int> arr;
29 vector<int> tree;
30 int n;
31
32 SegTree(vector<int>& arr){
33 this->arr = arr;
34 this->n = arr.size();
35 tree = vector<int>(this->n << 2, 0);
36 //tree[0] is meaningful
37 //left child: 2*i+1, right child: 2*i+2
38 }
39
40 void increase(int treeIdx, int l, int r, int ql, int qr, int num){
41 //increase [ql, qr] by 1
42 if(l > qr || ql > r){
43 return;
44 }
45
46 if(l == r){
47 if(arr[l] > num){
48 ++tree[treeIdx];
49 // cout << l << " : " << tree[treeIdx] << endl;
50 }
51 return;
52 }
53
54 int mid = (l+r) >> 1;
55
56 if(qr <= mid){
57 increase(treeIdx*2+1, l, mid, ql, qr, num);
58 }else if(ql > mid){
59 increase(treeIdx*2+2, mid+1, r, ql, qr, num);
60 }else{
61 increase(treeIdx*2+1, l, mid, ql, mid, num);
62 increase(treeIdx*2+2, mid+1, r, mid+1, qr, num);
63 }
64
65 tree[treeIdx] = tree[treeIdx*2+1]+tree[treeIdx*2+2];
66 }
67
68 int query(int treeIdx, int l, int r, int q){
69 if(l == r && l == q){
70 return tree[treeIdx];
71 }
72
73 int mid = (l+r) >> 1;
74
75 if(q <= mid){
76 return query(treeIdx*2+1, l, mid, q);
77 }else{
78 return query(treeIdx*2+2, mid+1, r, q);
79 }
80 }
81};
82
83class Solution {
84public:
85 vector<int> countSmaller(vector<int>& nums) {
86 int n = nums.size();
87
88 SegTree st(nums);
89
90 for(int i = 1; i < n; ++i){
91 st.increase(0, 0, n-1, 0, i-1, nums[i]);
92 }
93
94 vector<int> ans(n);
95
96 for(int i = 0; i < n; ++i){
97 ans[i] = st.query(0, 0, n-1, i);
98 }
99
100 return ans;
101 }
102};
103
104//Segment Tree with lazy propagation
105//TLE
106//15 / 16 test cases passed.
107class SegTree{
108public:
109 vector<int> arr;
110 vector<int> tree;
111 vector<vector<int>> lazy;
112 int n;
113
114 SegTree(vector<int>& arr){
115 this->arr = arr;
116 this->n = arr.size();
117 tree = vector<int>(this->n << 2, 0);
118 lazy = vector<vector<int>>(this->n << 2);
119 //tree[0] is meaningful
120 //left child: 2*i+1, right child: 2*i+2
121 }
122
123 void increase(int treeIdx, int l, int r, int ql, int qr, int num){
124 //increase [ql, qr] by 1
125 if(l > qr || ql > r){
126 return;
127 }
128
129 if(l == r){
130 if(arr[l] > num){
131 ++tree[treeIdx];
132 // cout << l << " : " << tree[treeIdx] << endl;
133 }
134 return;
135 }else if(ql == l && qr == r){
136 //lazy propagation
137 lazy[treeIdx].push_back(num);
138 // cout << "[" << l << ", " << r << "] lazy: ";
139 // for(int lznum : lazy[treeIdx]){
140 // cout << lznum << " ";
141 // }
142 // cout << endl;
143 return;
144 }
145
146 int mid = (l+r) >> 1;
147
148 if(qr <= mid){
149 increase(treeIdx*2+1, l, mid, ql, qr, num);
150 }else if(ql > mid){
151 increase(treeIdx*2+2, mid+1, r, ql, qr, num);
152 }else{
153 increase(treeIdx*2+1, l, mid, ql, mid, num);
154 increase(treeIdx*2+2, mid+1, r, mid+1, qr, num);
155 }
156
157 tree[treeIdx] = tree[treeIdx*2+1]+tree[treeIdx*2+2];
158 }
159
160 int query(int treeIdx, int l, int r, int q){
161 if(l == r){
162 /*
163 with lazy propagation,
164 we need to go to leaf node so the search is complete
165 */
166 return tree[treeIdx];
167 }
168
169 int mid = (l+r) >> 1;
170
171 int res;
172
173 if(q <= mid){
174 res = query(treeIdx*2+1, l, mid, q);
175 }else{
176 res = query(treeIdx*2+2, mid+1, r, q);
177 }
178
179 /*
180 after getting the result from leaf node,
181 we cannot directly return,
182 we still need to "merge" that result with
183 current internal node
184 */
185 // cout << "lz: ";
186 for(int lznum : lazy[treeIdx]){
187 // cout << lznum << " ";
188 if(arr[q] > lznum){
189 ++res;
190 }
191 }
192 // cout << endl;
193
194 return res;
195 }
196};
197
198class Solution {
199public:
200 vector<int> countSmaller(vector<int>& nums) {
201 int n = nums.size();
202
203 SegTree st(nums);
204
205 for(int i = 1; i < n; ++i){
206 // cout << "adding " << nums[i] << endl;
207 st.increase(0, 0, n-1, 0, i-1, nums[i]);
208 }
209
210 vector<int> ans(n);
211
212 for(int i = 0; i < n; ++i){
213 ans[i] = st.query(0, 0, n-1, i);
214 }
215
216 return ans;
217 }
218};
219
220//Segment Tree
221//use pointer rather than array, because treeIdx could be larger than n*4
222//https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76674/3-Ways-(Segment-Tree-Binary-Indexed-Tree-Merge-Sort)-clean-Java-code
223//Runtime: 36 ms, faster than 62.45% of C++ online submissions for Count of Smaller Numbers After Self.
224//Memory Usage: 11.4 MB, less than 52.47% of C++ online submissions for Count of Smaller Numbers After Self.
225class SegTreeNode{
226public:
227 //the values it covered's range: [vmin, vmax]
228 int vmin, vmax;
229 //how many values are covered
230 int count;
231 SegTreeNode *left, *right;
232
233 SegTreeNode(int vmin, int vmax){
234 this->vmin = vmin;
235 this->vmax = vmax;
236 count = 0;
237 left = right = nullptr;
238 }
239};
240
241class SegTree{
242public:
243 SegTreeNode* root;
244
245 SegTree(int vmin, int vmax){
246 root = new SegTreeNode(vmin, vmax);
247 }
248
249 void add(SegTreeNode* node, int val){
250 //tree[treeIdx]'s coverage: [node->vmin, node->vmax]
251
252 if(val < node->vmin || val > node->vmax){
253 //val is not in current node's coverage
254 return;
255 }
256
257 //add "val" to "node"'s coverage
258 ++node->count;
259 //it's leaf node
260 if(node->vmin == node->vmax) return;
261
262 //recursively update its descendants
263 int vmid = node->vmin + ((node->vmax - node->vmin) >> 1);
264 if(val <= vmid){
265 //go to left subtree
266 if(node->left == nullptr){
267 node->left = new SegTreeNode(node->vmin, vmid);
268 }
269 add(node->left, val);
270 }else{
271 //go to right subtree
272 if(node->right == nullptr){
273 node->right = new SegTreeNode(vmid+1, node->vmax);
274 }
275 add(node->right, val);
276 }
277 }
278
279 int find(SegTreeNode* node, int val){
280 //find the count of values <= val
281
282 if(node == nullptr){
283 //stop condition: current node the child of leaf node
284 return 0;
285 }
286
287 if(val >= node->vmax){
288 //the max element covered by node <= val
289 /*
290 we want to find values <= val,
291 and current node is in the range
292 */
293 return node->count;
294 }else{
295 //val < node->max
296 int vmid = node->vmin + ((node->vmax - node->vmin) >> 1);
297
298 if(val <= vmid){
299 /*
300 val falls in left subtree,
301 so don't need to search right subtree
302 */
303 return find(node->left, val);
304 }else{
305 /*
306 we are finding [INT_MIN, val],
307 so we need to find in left subtree
308 */
309 return find(node->left, val) + find(node->right, val);
310 }
311 }
312 }
313};
314
315class Solution {
316public:
317 vector<int> countSmaller(vector<int>& nums) {
318 int n = nums.size();
319 vector<int> ans(n);
320
321 if(n == 0) return ans;
322
323 // cout << "n: " << n << endl;
324
325 int vmin = *min_element(nums.begin(), nums.end());
326 int vmax = *max_element(nums.begin(), nums.end());
327
328 SegTree* st = new SegTree(vmin, vmax);
329
330 /*
331 in each iteration,
332 find nums[i]-1 before adding it to segment tree,
333 so when we find nums[i] in st,
334 all the elements in st are all after nums[i]
335 */
336 for(int i = n-1; i >= 0; --i){
337 //find count of values <= nums[i]-1
338 /*
339 now elements in st are nums[i+1:],
340 all behind current element,
341 so when searching in st,
342 we only care about elements' values,
343 don't need to care about their positions
344 */
345 ans[i] = st->find(st->root, nums[i]-1);
346 //add current element into st
347 //root's coverage: [vmin, vmax]
348 st->add(st->root, nums[i]);
349 }
350
351 return ans;
352 }
353};
354
355//Binary Indexed Tree
356//https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76674/3-Ways-(Segment-Tree-Binary-Indexed-Tree-Merge-Sort)-clean-Java-code
357//Runtime: 16 ms, faster than 96.71% of C++ online submissions for Count of Smaller Numbers After Self.
358//Memory Usage: 10.1 MB, less than 97.84% of C++ online submissions for Count of Smaller Numbers After Self.
359class BIT{
360public:
361 int n;
362 vector<int> tree;
363
364 BIT(int n){
365 //the index: 0 is meaningless
366 //the indices: [1,n] are meaningful
367 //we can retrieve count of values from the tree
368 this->n = n;
369 tree = vector<int>(n+1);
370 }
371
372 void increase(int i){
373 while(i <= n){
374 ++tree[i];
375 //left child is covered by its parent
376 //go to the upper node to its right
377 i += i&-i;
378 }
379 }
380
381 int get(int i){
382 //get count of numbers in [1, i]
383 int count = 0;
384
385 while(i > 0){
386 count += tree[i];
387 //go to the upper node just to its left
388 i -= i&-i;
389 }
390
391 return count;
392 }
393};
394
395class Solution {
396public:
397 vector<int> countSmaller(vector<int>& nums) {
398 int n = nums.size();
399 vector<int> ans(n);
400 if(n == 0) return ans;
401
402 /*
403 suppose nums's range is [a, b],
404 convert it to [1, b-a+1]
405 */
406 int minv = *min_element(nums.begin(), nums.end());
407 transform(nums.begin(), nums.end(), nums.begin(),
408 [&minv](int num){return num - minv + 1;});
409
410 int maxv = *max_element(nums.begin(), nums.end());
411
412 BIT* bit = new BIT(maxv);
413
414 for(int i = n-1; i >= 0; --i){
415 ans[i] = bit->get(nums[i]-1);
416 bit->increase(nums[i]);
417 }
418
419 return ans;
420 }
421};
422
423//mergesort
424//https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76674/3-Ways-(Segment-Tree-Binary-Indexed-Tree-Merge-Sort)-clean-Java-code
425//not understand
426//Runtime: 48 ms, faster than 51.32% of C++ online submissions for Count of Smaller Numbers After Self.
427//Memory Usage: 31.2 MB, less than 20.26% of C++ online submissions for Count of Smaller Numbers After Self.
428class Pair{
429public:
430 int idx;
431 int val;
432 Pair(int i, int v) : idx(i), val(v){};
433};
434
435class Solution {
436public:
437 void merge(vector<Pair*>& pairs, int start, int end, vector<int>& ans){
438 int mid = (start+end) >> 1;
439 vector<Pair*> newpairs(end-start+1);
440
441 // cout << "[" << start << ", " << mid << ", " << end << "]" << endl;
442 // for(int i = 0; i < pairs.size(); ++i){
443 // cout << pairs[i]->idx << " " << pairs[i]->val << " | ";
444 // }
445 // cout << endl;
446
447 //the index to left subarray
448 int lix = start;
449 //the index to right subarray
450 int rix = mid+1;
451 //the index to the new array: newpairs
452 int nix = 0;
453
454 while(nix < newpairs.size()){
455 // cout << lix << ", " << rix << ", " << nix << endl;
456 if(lix > mid || (rix <= end && pairs[rix]->val < pairs[lix]->val)){
457 /*
458 when lix == mid, it is still in the valid range of
459 left subarray,
460 only when lix > mid: we can say that
461 left subarray is totally visited
462 */
463 //choose from right subarray
464 // cout << "pick " << rix << endl;
465 newpairs[nix] = pairs[rix];
466 ++nix;
467 ++rix;
468 }else{
469 //choose from left subarray
470 /*
471 in right subarray,
472 [mid+1, rix-1] is already moved
473 to somewhere before nix,
474 their count is rix-mid-1
475 */
476 // cout << "pick " << lix << endl;
477 // cout << pairs[lix]->idx << " add " << rix-mid-1 << endl;
478 ans[pairs[lix]->idx] += rix - mid - 1;
479 newpairs[nix] = pairs[lix];
480 ++nix;
481 ++lix;
482 }
483 }
484 // cout << lix << ", " << rix << ", " << nix << endl;
485
486 copy_n(newpairs.begin(), end-start+1, pairs.begin()+start);
487 };
488
489 void mergesort(vector<Pair*>& pairs, int start, int end, vector<int>& ans){
490 if(end-start+1 <= 1) return;
491 int mid = (start+end) >> 1;
492
493 // cout << start << ", " << mid << ", " << end << endl;
494
495 mergesort(pairs, start, mid, ans);
496 mergesort(pairs, mid+1, end, ans);
497
498 merge(pairs, start, end, ans);
499 };
500
501 vector<int> countSmaller(vector<int>& nums) {
502 int n = nums.size();
503 vector<int> ans(n, 0);
504 if(n == 0) return ans;
505
506 vector<Pair*> pairs(n);
507
508 for(int i = 0; i < n; ++i){
509 pairs[i] = new Pair(i, nums[i]);
510 }
511
512 mergesort(pairs, 0, n-1, ans);
513
514 return ans;
515 }
516};
517
518//Binary Search Tree
519//https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76580/9ms-short-Java-BST-solution-get-answer-when-building-BST
520//Runtime: 16 ms, faster than 96.71% of C++ online submissions for Count of Smaller Numbers After Self.
521//Memory Usage: 20.4 MB, less than 37.38% of C++ online submissions for Count of Smaller Numbers After Self.
522class Node{
523public:
524 Node *left, *right;
525
526 int val, count, lbCount;
527
528 Node(int v, int lbc){
529 val = v;
530 //current node is inserted into the BST for "count" times
531 count = 1;
532 //count of nodes to the left and below current node
533 lbCount = lbc;
534 /*
535 to deal with the error:
536 member access within misaligned address ... for type 'Node',
537 which requires 8 byte alignment
538 */
539 left = right = nullptr;
540 }
541};
542
543class Solution {
544public:
545 Node* insert(Node* node, int cur, int num, int smallerCount, vector<int>& ans){
546 if(node == nullptr){
547 node = new Node(num, 0);
548 ans[cur] = smallerCount;
549 }else if(node->val == num){
550 ++node->count;
551 ans[cur] = smallerCount + node->lbCount;
552 }else if(num < node->val){
553 ++node->lbCount;
554 node->left = insert(node->left, cur, num, smallerCount, ans);
555 }else{
556 /*
557 because num > node->val,
558 (the num to be inserted is larger than current node),
559 so we accumulate node->count and node->lbCount to smallerCount
560 */
561 node->right = insert(node->right, cur, num,
562 smallerCount+node->count+node->lbCount , ans);
563 }
564
565 return node;
566 };
567
568 vector<int> countSmaller(vector<int>& nums) {
569 int n = nums.size();
570 Node* root = nullptr;
571
572 vector<int> ans(n);
573
574 for(int i = n-1; i >= 0; --i){
575 root = insert(root, i, nums[i], 0, ans);
576 }
577
578 return ans;
579 }
580};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
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.