#1505

Hard

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Possible Integer After at Most K Adjacent Swaps On Digits

Reorder digits using at most k adjacent swaps to produce the smallest possible integer, leveraging greedy selection efficiently.

string greedy binary indexed tree segment tree

Problem Statement

You are given a string num representing a large integer and an integer k. You can swap any two adjacent digits at most k times. Your task is to reorder the digits using these swaps to obtain the smallest possible integer and return it as a string.

For example, given num = "4321" and k = 4, strategic adjacent swaps can move smaller digits toward the front, resulting in "1342". Note that leading zeros are allowed in the result, but the input is guaranteed to have no leading zeros.

Examples

Example 1

Input: num = "4321", k = 4

Output: "1342"

The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.

Example 2

Input: num = "100", k = 1

Output: "010"

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"

We can keep the number without any swaps.

Constraints

1 <= num.length <= 3 * 104
num consists of only digits and does not contain leading zeros.
1 <= k <= 109

Solution Approach

Greedy Selection of Minimum Digits

Iterate through each position and identify the smallest digit within the range allowed by remaining swaps k. Swap that digit toward the current position, decrementing k by the distance moved. This maintains the invariant that the current choice uses swaps efficiently.

Efficient Swap Tracking with BIT

Use a Binary Indexed Tree to track the number of swaps needed to move a digit to its target position. This ensures that each greedy choice does not exceed the remaining k and helps handle large inputs within acceptable time.

Handling Edge Cases and Large k

If k is large enough to allow full sorting, the greedy selection still applies but may terminate early. Leading zeros in the resulting string are acceptable, and digits already in optimal order should be skipped to save unnecessary swap computation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the method: naive greedy can be O(n*k), but using a BIT or Segment Tree can reduce it to O(n log n). Space complexity is mainly for the BIT or Segment Tree, roughly O(n).

What Interviewers Usually Probe

Ask candidates to justify why moving the smallest available digit first minimizes the integer.
Expect them to explain handling of swaps exceeding remaining k and edge cases with leading zeros.
Look for awareness of data structures like BIT or Segment Tree for efficient tracking of swap costs.

Common Pitfalls or Variants

Common pitfalls

Attempting to swap digits greedily without considering remaining k, which may exceed limits.
Ignoring the impact of leading zeros on the result string.
Recomputing swap counts naively, causing timeouts on large inputs.

Follow-up variants

Allow swaps between any two digits instead of only adjacent, changing the approach to direct sorting.
Limit k to very small numbers to emphasize careful local greedy choices rather than global movement.
Modify the problem to maximize the integer instead of minimizing, applying the same greedy invariant in reverse.

FAQ

What is the main pattern to solve Minimum Possible Integer After at Most K Adjacent Swaps On Digits?

The problem follows a greedy choice plus invariant validation pattern: always move the smallest feasible digit to the current position without exceeding k swaps.

Can the result have leading zeros?

Yes, leading zeros are allowed in the output string, even though the input is guaranteed to have none.

Which data structures optimize this problem for large inputs?

Binary Indexed Trees or Segment Trees efficiently track swap counts and support fast greedy digit selection.

What is the time complexity when using BIT?

Using a BIT, each digit selection and move can be processed in O(log n), giving an overall complexity of O(n log n).

How should I handle k larger than the number of swaps needed?

Once k is sufficient to fully order the digits, greedy selection still applies, and remaining swaps are unused; no extra handling is needed.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.c = [0] * (n + 1)

    @staticmethod
    def lowbit(x):
        return x & -x

    def update(self, x, delta):
        while x <= self.n:
            self.c[x] += delta
            x += BinaryIndexedTree.lowbit(x)

    def query(self, x):
        s = 0
        while x:
            s += self.c[x]
            x -= BinaryIndexedTree.lowbit(x)
        return s


class Solution:
    def minInteger(self, num: str, k: int) -> str:
        pos = defaultdict(deque)
        for i, v in enumerate(num, 1):
            pos[int(v)].append(i)
        ans = []
        n = len(num)
        tree = BinaryIndexedTree(n)
        for i in range(1, n + 1):
            for v in range(10):
                q = pos[v]
                if q:
                    j = q[0]
                    dist = tree.query(n) - tree.query(j) + j - i
                    if dist <= k:
                        k -= dist
                        q.popleft()
                        ans.append(str(v))
                        tree.update(j, 1)
                        break
        return ''.join(ans)

Continue Practicing

#2193 minimum number of moves to make palindrome #1520 maximum number of non overlapping substrings #1529 minimum suffix flips