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.
This approach makes use of a greedy algorithm. The idea is to always try to bring the smallest possible digit to the front using the allowed adjacent swaps.
By iterating through the digits of the number, for each position, determine the smallest digit within a distance of k. Then perform the necessary swaps to bring that smallest digit to the current position.
This approach minimizes the resulting integer by always prioritizing the smallest digit to be swapped forward.
We maintain the string as a list for in-place modifications. For each index, find the minimum digit within the next k positions and swap it forward. Update k for the swaps made and break if k runs out.
Time Complexity: O(n*k) in the worst case where k is large.
Space Complexity: O(n) due to the storage of digits.
This approach uses a Segment Tree to efficiently find the minimum digit within a segment of the number in logarithmic time. It allows us to store and update the position of digits dynamically.
The Segment Tree helps in reducing the computational bottleneck of finding the minimum digit that can be swapped to the front within 'k' swaps, from linear to log time complexity per query.
This solution is implemented using a Segment Tree wrapped into a class. It builds the tree and uses it to find the minimum index efficiently, re-building as adjustments are made.
C++
JavaScript
Time Complexity: O(n log n) due to segment tree operations.
Space Complexity: O(n) due to the segment tree structure.
| Approach | Complexity |
|---|---|
| Greedy Approach with Permutation Indices | Time Complexity: O(n*k) in the worst case where k is large. |
| Using Segment Tree for Efficient Minimum Finding | Time Complexity: O(n log n) due to segment tree operations. |
| Default Approach | — |
| 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. |
1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits (Leetcode Hard) • Programming Live with Larry • 1,893 views views
Watch 6 more video solutions →Practice Minimum Possible Integer After at Most K Adjacent Swaps On Digits with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor