Minimum Possible Integer After at Most K Adjacent Swaps On Digits Python/Java solution

Python and Java implementations usually follow the greedy + Fenwick Tree strategy. Maintain queues for each digit (0–9), select the smallest reachable digit, compute its swap cost using prefix sums from the tree, and update the structure after placing the digit. This ensures O(n log n) performance.

What is the best approach for Minimum Possible Integer After at Most K Adjacent Swaps On Digits?

The best approach uses a greedy strategy combined with a Binary Indexed Tree (Fenwick Tree). At each position, choose the smallest digit that can be moved to the front using at most k swaps. The Fenwick Tree tracks how many digits have already shifted so the effective swap distance can be computed quickly. This solution runs in O(n log n) time with O(n) space.

Is Minimum Possible Integer After at Most K Adjacent Swaps On Digits asked at Google/Amazon/Meta?

Problems involving greedy digit selection with Fenwick Trees or segment trees frequently appear in interviews at companies like Google, Amazon, and Meta. This specific LeetCode problem is considered a high-level interview question because it combines greedy reasoning with advanced data structures.

What data structure is used in Minimum Possible Integer After at Most K Adjacent Swaps On Digits?

The most common data structures used are a Binary Indexed Tree (Fenwick Tree) and sometimes a Segment Tree. They help track how many digits have been removed or shifted so the effective swap distance can be calculated efficiently during the greedy selection process.

What is the time complexity of Minimum Possible Integer After at Most K Adjacent Swaps On Digits?

The optimal solution runs in O(n log n) time. Each digit selection requires logarithmic updates and prefix queries in a Binary Indexed Tree or Segment Tree. Space complexity is O(n) for storing digit positions and maintaining the tree structure.

Description Hints 2 Solution Video 28:19

1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits

Q: How to solve Minimum Possible Integer After at Most K Adjacent Swaps On Digits in O(n)?

A strict O(n) solution is generally not feasible because the algorithm must repeatedly update and query positions after swaps. Efficient implementations rely on a Binary Indexed Tree or Segment Tree, which reduces operations to O(log n). The resulting complexity becomes O(n log n), which is considered optimal for this problem.

Hard41.8% acceptance1 company

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 * 10⁴
num consists of only digits and does not contain leading zeros.
1 <= k <= 10⁹

Asked at 1 company

Hashedin

Topics

Hints open one at a time

Hint 1

We want to make the smaller digits the most significant digits in the number.

Hint 2

For each index i, check the smallest digit in a window of size k and append it to the answer. Update the indices of all digits in this range accordingly.

28:19

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minInteger(self, num: str, k: int) -> str:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"4321"
4

Input

"100"
1

Input

"36789"
1000

Your code is saved on this device.Solution