A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 164. Maximum Gap, the solution in this repository is mainly a prefix sums 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: prefix sums, greedy.
The notes already sitting in the source point us in the right direction:
- sorting
- time: O(NlogN)
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 maximumGap, radixSort, tmp, counter, counter_acc.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- 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(NlogN)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//sorting
02//Runtime: 8 ms, faster than 98.12% of C++ online submissions for Maximum Gap.
03//Memory Usage: 8.9 MB, less than 10.99% of C++ online submissions for Maximum Gap.
04//time: O(NlogN)
05class Solution {
06public:
07 int maximumGap(vector<int>& nums) {
08 int n = nums.size();
09 if(n < 2) return 0;
10
11 sort(nums.begin(), nums.end());
12
13 int ans = 0;
14
15 for(int i = 1; i < n; ++i){
16 ans = max(ans, nums[i] - nums[i-1]);
17 }
18
19 return ans;
20 }
21};
22
23//radix sort
24//https://openhome.cc/Gossip/AlgorithmGossip/RadixSort.htm
25//Runtime: 20 ms, faster than 22.30% of C++ online submissions for Maximum Gap.
26//Memory Usage: 12.7 MB, less than 10.99% of C++ online submissions for Maximum Gap.
27class Solution {
28public:
29 void radixSort(vector<int>& nums){
30 vector<vector<int>> buckets(10);
31
32 int max_digit = 1 + log10(*max_element(nums.begin(), nums.end()));
33
34 //least significant digital
35 for(int digit = 1; digit <= max_digit; ++digit){
36 for(const int& num : nums){
37 buckets[num%(int)pow(10, digit)/pow(10, digit-1)].push_back(num);
38 }
39
40 vector<int> tmp;
41
42 for(const vector<int>& bucket : buckets){
43 tmp.insert(tmp.end(), bucket.begin(), bucket.end());
44 }
45
46 nums.swap(tmp);
47 buckets = vector<vector<int>>(10);
48 }
49
50 }
51
52 int maximumGap(vector<int>& nums) {
53 int n = nums.size();
54 if(n < 2) return 0;
55
56 radixSort(nums);
57
58 // for(int num : nums){
59 // cout << num << " ";
60 // }
61 // cout << endl;
62
63 int ans = 0;
64
65 for(int i = 1; i < n; ++i){
66 ans = max(ans, nums[i] - nums[i-1]);
67 }
68
69 return ans;
70 }
71};
72
73//Approach 2: Radix Sort(official)
74//Radix sort uses Counting sort as a subroutine.
75//Runtime: 16 ms, faster than 48.38% of C++ online submissions for Maximum Gap.
76//Memory Usage: 9.1 MB, less than 10.99% of C++ online submissions for Maximum Gap.
77// radix sort: time: O(d*(n+radix)), space: O(n)
78// counting sort: time: O(n + radix), space: O(radix)
79class Solution {
80public:
81 void radixSort(vector<int>& nums){
82 int exp = 1;
83 int radix = 10;
84
85 int maxVal = *max_element(nums.begin(), nums.end());
86
87 vector<int> tmp(nums.size());
88
89 while(maxVal/exp > 0){
90 // counting sort to sort current digit
91 vector<int> counter(radix, 0);
92
93 for(const int& num : nums){
94 //say exp = pow(radix, p), then (num/exp)%radix is pth digit
95 ++counter[(num/exp)%radix];
96 }
97
98 vector<int> counter_acc(counter.size());
99 /*
100 this is just like:
101 for(int i = 1; i < radix; ++i){
102 counter[i] += counter[i-1];
103 }
104 */
105 partial_sum(counter.begin(), counter.end(), counter_acc.begin());
106
107 //fill from begin: so the sorting is stable
108 for(auto it = nums.rbegin(); it != nums.rend(); ++it){
109 tmp[--counter_acc[(*it/exp)%radix]] = *it;
110 }
111
112 swap(nums, tmp);
113
114 exp *= 10;
115 }
116 }
117
118 int maximumGap(vector<int>& nums) {
119 int n = nums.size();
120 if(n < 2) return 0;
121
122 radixSort(nums);
123
124 // for(int num : nums){
125 // cout << num << " ";
126 // }
127 // cout << endl;
128
129 int ans = 0;
130
131 for(int i = 1; i < n; ++i){
132 ans = max(ans, nums[i] - nums[i-1]);
133 }
134
135 return ans;
136 }
137};
138
139//Approach 3: Buckets and The Pigeonhole Principle
140//Runtime: 12 ms, faster than 84.36% of C++ online submissions for Maximum Gap.
141//Memory Usage: 9.2 MB, less than 10.95% of C++ online submissions for Maximum Gap.
142//time: O(n + b) = O(n)
143//space: O(b*2) = O(b)
144struct Bucket{
145 bool used;
146 int maxv, minv;
147
148 Bucket(): used(false), minv(INT_MAX), maxv(INT_MIN) {};
149};
150
151class Solution {
152public:
153 int maximumGap(vector<int>& nums) {
154 int n = nums.size();
155
156 if(n <= 1) return 0;
157
158 int maxn = *max_element(nums.begin(), nums.end());
159 int minn = *min_element(nums.begin(), nums.end());
160
161 /*
162 we can get min possible gap by assuming
163 the n elements are uniformly distributed in [minn, maxn]
164
165 e.g. [1,4,7,10]: max gap = 3,
166 if the array is not uniformly distrubted,
167 e.g. [1,3,7,10]: the max gap will become 4
168 */
169 double min_possible_gap = (double)(maxn - minn)/(n-1);
170
171 /*
172 the gap in a bucket will be bucket_size-1,
173 by setting bucket size be <= min_possible_gap,
174 we know that the gap in any bucket will < min_possible_gap,
175 so we only need to find max gap at two buckets's boundary,
176 not need to find within buckets
177 */
178 //bucket_size should be at least 1
179 int bucket_size = max(1, (int)floor(min_possible_gap));
180
181 int bucket_count = ceil((double)(1LL + maxn - minn)/bucket_size);
182
183 vector<Bucket> buckets(bucket_count);
184
185 for(int& num : nums){
186 int bucket_id = (num-minn)/bucket_size;
187 buckets[bucket_id].used = true;
188 buckets[bucket_id].minv = min(buckets[bucket_id].minv, num);
189 buckets[bucket_id].maxv = max(buckets[bucket_id].maxv, num);
190 }
191
192 int max_gap = 0;
193 int last_maxv = buckets[0].minv;
194 for(Bucket& bucket : buckets){
195 //ignore empty bucket
196 if(!bucket.used) continue;
197 max_gap = max(max_gap, bucket.minv - last_maxv);
198 last_maxv = bucket.maxv;
199 }
200
201 // cout << max_gap << endl;
202
203 return max_gap;
204 }
205};Cost
Complexity
Time
O(NlogN)
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.