2
$\begingroup$

This problem is from LeetCode.

You're 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.

My question is, why does the following greedy algorithm work?

minimum_integer(num, k):
    n <- length of num
    i <- 0
    while i < n and k > 0:
        pos <- position of the first smallest element in num[i..min(n-1, i + k)]
        while pos > i:
            swap pos and pos-1 of num
            decrease pos by 1
            decrease k by 1
        increase i by 1
    return num

The algorithm makes sense intuitively; we essentially move the minimum digit in a window of size at most k into each possible position, and since we minimize leading digits each time starting from the first leading digit, it makes intuitive sense that the resulting number should be minimized. But I'm not sure how to prove it produces an optimal solution using an exchange argument.

$\endgroup$
5
  • $\begingroup$ Where did you get this solution and what is $n$? $\endgroup$
    – Russel
    Apr 9, 2022 at 2:43
  • $\begingroup$ @Russel it's based off a solution from the link I provided. I basically just converted it to pseudocode. $\endgroup$
    – user3472
    Apr 9, 2022 at 12:27
  • 1
    $\begingroup$ This code is not performing swaps ! $\endgroup$
    – user16034
    Apr 9, 2022 at 16:28
  • $\begingroup$ @YvesDaoust Good catch. Updated. $\endgroup$
    – John L.
    Apr 9, 2022 at 19:01
  • $\begingroup$ @YvesDaoust the previous code actually did perform swaps. It just did it in a different way through shifting. $\endgroup$
    – user3472
    Apr 9, 2022 at 20:22

1 Answer 1

2
$\begingroup$

Let $A$ be the greedy algorithm you presented and $A'$ be the algorithm that correctly solves the problem.

Let $m=d_{n-1}d_{n-2}d_{n-3}...d_2d_1d_0$ be the solution obtained by $A$ and $m'=d'_{n-1}d'_{n-2}d'_{n-3}...d'_2d'_1d'_0$ be the number obtained by $A'$.

First, some observation about $A$. For each index $0 \le j \le n-1$, $A$ select that smallest digit from indices $\le j$ that can be placed at index $j$ using the remaining number of moves. This implies that once a digit is in-place, it remains in its position until the end. Now, the number of swaps $A$ uses to move a digit initially at index $i$ is $j - i$, which is the minimum possible if swapping adjacent digits is the only allowed move. Therefore, $A$ uses the minimum possible moves to place a digit to its place.

Let $i$ be the last index that $A$ updated before it exhaust all the remaining moves. Because $A$ selects the minimum digit that can be placed at index $j \ge i$ using the minimum number of moves while not exceeding the available moves, it must be that $d_j = d'_j$ for $i \le j \le n-1$. Now, since $A$ uses the minimum number of moves possible to move a digit to its final position, the total number of moves $A'$ uses to change all index $j \ge i$ cannot be less than the total number of moves used by $A$. Therefore, both $A$ and $A'$ cannot change any remaining index less than $i$, thus $d_j = d'_j$ for $0 \le j \le i-1$. Finally, $m = m'$.

$\endgroup$
1
  • $\begingroup$ Does this answer mention that different moving order will not affect the number of total adjacent swaps used? For example, the same number of adjacent swaps will be used whether $d_3$ is moved to index 0 and then $d_2$ is moved to index 1 or $d_2$ is moved to index 1 and then $d_3$ is moved to index 0 and then $d_2$ is moved to index 1 , assuming $n\ge 6$. Or does it? $\endgroup$
    – John L.
    Apr 9, 2022 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.