I like to read this solution as a small machine: keep the useful information, throw away the noise. For 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits, the solution in this repository is mainly a binary search solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. 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:
- TLE
- 48 / 51 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 minInteger, update, increase, query, queryLessThan.
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 queue gives the solution a level-by-level or frontier-style traversal.
- Substring checks are convenient but not free, so they are part of the real complexity story.
- 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:
- 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(N^2)
- 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//48 / 51 test cases passed.
03class Solution {
04public:
05 string minInteger(string num, int k) {
06 int n = num.size();
07 for(int i = 0; i < n && k > 0; ++i){
08 //find the smallest number in window size k
09 //[i:i+k]
10 // cout << "i: " << i << endl;
11 auto min_it = min_element(num.begin()+i, num.begin()+min(n, i+k+1));
12
13 if(*min_it < num[i]){
14 //do swap
15 int min_idx = min_it - num.begin();
16 //[0,i-1] + [i, min_idx], [min_idx+1,n-1]
17 //num = num.substr(0, i) + *min_it + num.substr(i, min_idx-i) + num.substr(min_idx+1);
18 // cout << "i: " << i << ", min_idx: " << min_idx << endl;
19 // cout << num << "->";
20 num.replace(i, min_idx-i+1, *min_it + num.substr(i, min_idx-i));
21 // cout << num << endl;
22 //swap from min_idx to i, that is (min_idx - i) times
23 k -= (min_idx - i);
24 }
25 }
26
27 return num;
28 }
29};
30
31//recursion
32//https://leetcode.com/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits/discuss/720215/The-constraint-was-not-very-helpful...-C%2B%2BPython-Clean-56ms-O(n2)-solution
33//TLE
34//50 / 51 test cases passed.
35//time: O(N^2)
36class Solution {
37public:
38 string minInteger(string num, int k) {
39 if(k <= 0) return num;
40
41 int n = num.size();
42
43 if(k >= n*(n-1)/2){
44 sort(num.begin(), num.end());
45 return num;
46 }
47
48 //find '0'~'9'
49 for(int i = 0; i < 10; ++i){
50 int idx = num.find(to_string(i));
51 if(idx >= 0 && idx <= k){
52 //k-idx: move the char from idx to 0 cost "idx" swaps
53 return num[idx] + minInteger(num.substr(0, idx) + num.substr(idx+1), k - idx);
54 }
55 }
56
57 return num;
58 }
59};
60
61//Segment tree
62//https://leetcode.com/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits/discuss/720548/O(n-logn)-or-Java-or-Heavily-Commented-or-Segment-Tree-or-Detailed-Explanation
63//Runtime: 184 ms, faster than 52.63% of C++ online submissions for Minimum Possible Integer After at Most K Adjacent Swaps On Digits.
64//Memory Usage: 13.3 MB, less than 100.00% of C++ online submissions for Minimum Possible Integer After at Most K Adjacent Swaps On Digits.
65//time: O(NlogN)
66class SegTree{
67public:
68 vector<int> nodes;
69 int n;
70
71 SegTree(int n){
72 this->n = n;
73 nodes = vector<int>(this->n << 2);
74 }
75
76 void update(int treeIdx, int l, int r, int ql, int val){
77 //update [ql,ql]
78 if(ql < l || ql > r){
79 return;
80 }
81
82 if(l == r){
83 //leaf node
84 nodes[treeIdx] += val;
85 // cout << "nodes[" << treeIdx << "] = " << nodes[treeIdx] << endl;
86 return;
87 }
88
89 int mid = (l+r)/2;
90
91 if(ql <= mid){
92 //update left subtree
93 update(treeIdx*2+1, l, mid, ql, val);
94 }else{
95 update(treeIdx*2+2, mid+1, r, ql, val);
96 }
97
98 nodes[treeIdx] = nodes[treeIdx*2+1] + nodes[treeIdx*2+2];
99 // cout << "nodes[" << treeIdx << "] = " << nodes[treeIdx] << endl;
100 }
101
102 void increase(int ql){
103 update(0, 0, n-1, ql, 1);
104 }
105
106 int query(int treeIdx, int l, int r, int ql, int qr){
107 if(l > qr || r < ql){
108 return 0;
109 }
110
111 if(ql <= l && r <= qr){
112 //looking range is inside query range
113 return nodes[treeIdx];
114 }
115
116 int mid = (l+r)/2;
117
118 if(qr <= mid){
119 //complete in left subtree
120 return query(treeIdx*2+1, l, mid, ql, qr);
121 }else if(ql > mid){
122 //complete in right subtree
123 return query(treeIdx*2+2, mid+1, r, ql, qr);
124 }
125
126 int leftRes = query(treeIdx*2+1, l, mid, ql, mid);
127 int rightRes = query(treeIdx*2+2, mid+1, r, mid+1, qr);
128
129 return leftRes + rightRes;
130 }
131
132 int queryLessThan(int qnum){
133 return query(0, 0, n-1, 0, qnum-1);
134 }
135};
136
137class Solution {
138public:
139 string minInteger(string num, int k) {
140 //0-9's locations in "num"
141 vector<queue<int>> qs(10);
142 int n = num.size();
143
144 for(int i = 0; i < n; ++i){
145 qs[num[i]-'0'].push(i);
146 }
147
148 string ans;
149 SegTree* tree = new SegTree(n);
150
151 for(int i = 0; i < n; ++i){
152 for(int d = 0; d <= 9; ++d){
153 /*
154 qs[d]: contains the positions of unshifted digit d
155 */
156 if(!qs[d].empty()){
157 //the nearest d's position
158 int pos = qs[d].front();
159 /*
160 how many digits in front of pos is
161 already shifted to its right position
162 */
163 int shifted = tree->queryLessThan(pos);
164 /*
165 move from "pos" to the index "shifted"
166 */
167 if(pos - shifted <= k){
168 k -= pos-shifted;
169 //the digit originally in pos has been shifted
170 tree->increase(pos);
171 qs[d].pop();
172 ans += ('0'+d);
173 break;
174 }
175 }
176 }
177 }
178
179 return ans;
180 }
181};
182
183//segment tree, optimized
184//https://leetcode.com/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits/discuss/720548/O(n-logn)-or-Java-or-Heavily-Commented-or-Segment-Tree-or-Detailed-Explanation/606367
185//Runtime: 92 ms, faster than 75.82% of C++ online submissions for Minimum Possible Integer After at Most K Adjacent Swaps On Digits.
186//Memory Usage: 13.9 MB, less than 100.00% of C++ online submissions for Minimum Possible Integer After at Most K Adjacent Swaps On Digits.
187//time: O(NlogN)
188class SegTree{
189public:
190 vector<int> nodes;
191 int n;
192
193 SegTree(int n){
194 this->n = n;
195 nodes = vector<int>(this->n << 2);
196 }
197
198 void update(int treeIdx, int l, int r, int ql, int val){
199 if(ql < l || ql > r){
200 return;
201 }
202
203 if(l == r){
204 nodes[treeIdx] += val;
205 return;
206 }
207
208 int mid = (l+r) >> 1;
209
210 if(ql <= mid){
211 update((treeIdx<<1)|1, l, mid, ql, val);
212 }else{
213 update((treeIdx<<1)+2, mid+1, r, ql, val);
214 }
215
216 nodes[treeIdx] = nodes[(treeIdx<<1)|1] + nodes[(treeIdx<<1)+2];
217 }
218
219 void increase(int ql){
220 update(0, 0, n-1, ql, 1);
221 }
222
223 int query(int treeIdx, int l, int r, int ql, int qr){
224 if(l > qr || r < ql){
225 return 0;
226 }
227
228 if(ql <= l && r <= qr){
229 return nodes[treeIdx];
230 }
231
232 int mid = (l+r) >> 1;
233
234 if(qr <= mid){
235 return query((treeIdx<<1)|1, l, mid, ql, qr);
236 }else if(ql > mid){
237 return query((treeIdx<<1)+2, mid+1, r, ql, qr);
238 }
239
240 int leftRes = query((treeIdx<<1)|1, l, mid, ql, mid);
241 int rightRes = query((treeIdx<<1)+2, mid+1, r, mid+1, qr);
242
243 return leftRes + rightRes;
244 }
245
246 int queryLessThan(int qnum){
247 return query(0, 0, n-1, 0, qnum-1);
248 }
249};
250
251class Solution {
252public:
253 string minInteger(string num, int k) {
254 vector<queue<int>> qs(10);
255 int n = num.size();
256
257 for(int i = 0; i < n; ++i){
258 qs[num[i]-'0'].push(i);
259 }
260
261 string lhs;
262 vector<bool> removed(n, false);
263 SegTree* tree = new SegTree(n);
264
265 while(k > 0){
266 bool found = false;
267 for(int d = 0; d <= 9; ++d){
268 if(!qs[d].empty()){
269 int pos = qs[d].front();
270 int shifted = tree->queryLessThan(pos);
271 if(pos - shifted <= k){
272 k -= pos-shifted;
273 tree->increase(pos);
274 qs[d].pop();
275 lhs += ('0'+d);
276 removed[pos] = true;
277 found = true;
278 break;
279 }
280 }
281 }
282 if(!found) break;
283 }
284
285 string rhs;
286 for(int i = 0; i < n; ++i){
287 if(!removed[i]){
288 rhs += num[i];
289 }
290 }
291
292 return lhs + rhs;
293 }
294};
295
296//Binary Indexed Tree
297//since query range all start from 0, and the query indices are in ascending order, so we can rewrite it as BIT?
298//https://leetcode.com/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits/discuss/720548/O(n-logn)-or-Java-or-Heavily-Commented-or-Segment-Tree-or-Detailed-Explanation/606367
299//Runtime: 60 ms, faster than 90.59% of C++ online submissions for Minimum Possible Integer After at Most K Adjacent Swaps On Digits.
300//Memory Usage: 11.6 MB, less than 100.00% of C++ online submissions for Minimum Possible Integer After at Most K Adjacent Swaps On Digits.
301//time: O(NlogN)
302class BIT{
303public:
304 int n;
305 vector<int> nodes;
306
307 BIT(int n){
308 this->n = n;
309 nodes = vector<int>(n+1);
310 }
311
312 void update(int i, int delta){
313 ++i;
314 while(i <= n){
315 nodes[i] += delta;
316 i += (i&-i);
317 }
318 }
319
320 int query(int i){
321 ++i;
322 int sum = 0;
323
324 while(i > 0){
325 sum += nodes[i];
326 i -= (i&-i);
327 }
328
329 return sum;
330 }
331};
332
333class Solution {
334public:
335 string minInteger(string num, int k) {
336 vector<queue<int>> qs(10);
337 int n = num.size();
338
339 for(int i = 0; i < n; ++i){
340 qs[num[i]-'0'].push(i);
341 }
342
343 string lhs;
344 vector<bool> removed(n, false);
345 BIT* tree = new BIT(n);
346
347 while(k > 0){
348 bool found = false;
349 for(int d = 0; d <= 9; ++d){
350 if(!qs[d].empty()){
351 int pos = qs[d].front();
352 int shifted = tree->query(pos-1);
353 if(pos - shifted <= k){
354 k -= pos-shifted;
355 tree->update(pos, 1);
356 qs[d].pop();
357 lhs += ('0'+d);
358 removed[pos] = true;
359 found = true;
360 break;
361 }
362 }
363 }
364 if(!found) break;
365 }
366
367 string rhs;
368 for(int i = 0; i < n; ++i){
369 if(!removed[i]){
370 rhs += num[i];
371 }
372 }
373
374 return lhs + rhs;
375 }
376};Cost
Complexity
Time
O(N^2)
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.