Watch 7 video solutions for Minimum Possible Integer After at Most K Adjacent Swaps On Digits, a hard level problem involving String, Greedy, Binary Indexed Tree. This walkthrough by Programming Live with Larry has 1,893 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string num representing the digits of a very large integer and an integer k. You are allowed to swap any two adjacent digits of the integer at most k times.
Return the minimum integer you can obtain also as a string.
Example 1:
Input: num = "4321", k = 4 Output: "1342" Explanation: The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.
Example 2:
Input: num = "100", k = 1 Output: "010" Explanation: It's ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.
Example 3:
Input: num = "36789", k = 1000 Output: "36789" Explanation: We can keep the number without any swaps.
Constraints:
1 <= num.length <= 3 * 104num consists of only digits and does not contain leading zeros.1 <= k <= 109Problem Overview: You are given a numeric string num and an integer k. Each operation swaps two adjacent digits, and you can perform at most k swaps. The goal is to produce the lexicographically smallest possible integer after these swaps.
Approach 1: Greedy with Permutation Indices + Binary Indexed Tree (O(n log n) time, O(n) space)
The key observation is that the leftmost digits have the greatest impact on the final number. At each position, try to bring the smallest possible digit forward if it can reach the current position within the remaining swap budget. Maintain queues of indices for digits 0–9. For each candidate digit, compute how many swaps are needed to move its next occurrence to the current position.
A Binary Indexed Tree (Fenwick Tree) tracks how many digits have already been moved. This allows you to adjust the effective index after previous shifts. If the required swaps are ≤ k, move that digit to the result, update the tree, reduce k, and continue. The strategy works because a greedy choice of the smallest reachable digit always leads to the optimal prefix.
Approach 2: Segment Tree for Efficient Minimum Finding (O(n log n) time, O(n) space)
Another way to implement the same greedy idea is with a segment tree. Instead of scanning digits 0–9 each step, build a segment tree that stores the minimum digit available in a range along with its index. The tree supports queries to find the smallest digit that can be moved to the current position without exceeding the remaining swaps.
When a digit is selected, update the tree to mark its index as used and adjust swap counts accordingly. The segment tree efficiently handles repeated minimum queries and updates in O(log n). This approach is especially useful in languages where priority structures or index bookkeeping becomes complex.
Recommended for interviews: The greedy strategy combined with a Binary Indexed Tree is the expected optimal solution. It demonstrates understanding of lexicographic minimization, index shifting caused by swaps, and efficient prefix counting. Segment trees solve the same problem but are usually considered an alternative implementation. Showing the greedy reasoning first, then implementing it with a Fenwick Tree, signals strong algorithmic maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Binary Indexed Tree | O(n log n) | O(n) | Best general solution. Efficiently tracks index shifts caused by swaps. |
| Greedy with Segment Tree | O(n log n) | O(n) | Useful when implementing range minimum queries and updates together. |