Algorithm to find smallest integer by swapping a pair of digits in given integer

Question

Given a positive integer (in the form of an array of digits). We are allowed to swap one pair of digits in the given number. We need to return the smallest possible integer that can be obtained. Note, it should be a valid integer, i.e, should not contain leading 0's.

For example:-

1. 93561 returns 13569
2. 596 returns 569
3. 10234 returns 10234
4. 120 returns 102
5. 10091 returns 10019
6. 98761111 returns 18761119

Is there an O(n) algorithm for this problem. I have thought of few ways for this :-

1. Find the min. digit (minDIgit) in the given integer (except 0) and swap it with the MSB, if MSB != minDigit. If MSB==minDigit, then find the next min. digit and swap it with the most significant but 1 digit and so on. This could be O(n^2) in worst case.
2. Make an array/vector of std::pair of digit and index and sort it in increasing order (according to digit values; keep lower indices first for matching digit values). Iterate through the sorted array. Swap the MSB with the first digit. If the least digit has corresponding index as MSB, then swap the MSB but 1 place with the next min digit. If the next min digit has corresponding index of MSB but 1 place, then swap the MSB but 2 place with this next min. digit and so on. This should be O(nlog(n)).

Can someone suggest a better algorithm.

---

UPDATE 1: After thinking a bit, second algo which I proposed would work perfectly fine (probably except few corner cases, which can be handled separately). Moreover, I can sort the pair(digit, index) using counting sort (according to digit values), which is a stable sort in O(n) time. Is there a flaw in my argument?

---

UPDATE 2: My 2nd algo would work (although with more checks for corner cases and 0's) and that too in O(n) time with counting sort. But solution given by @GaborSch is much simpler, so I won't really bother giving a proper code for my algo.

Answer 1

As a preparation, we loop through the digits, and mark the last positions of the digits in an array[10] (call it last) (including 0s). That is O(n).

Next, we start to iterate through digits from left to right. For each position we try to find the smallest digit whose last position is greater than our current position (position constraint). Also that digit must be smaller than the current digit.

If we are in the first position we start the loop on last from 1 (otherwise from 0), just until the value of the current digit (not including).

If we find such a digit (concerning the position constraint), we swap (and break the loop). If we don't, we go forward to the next digit. The cost is at most O(n*9), which is O(n).

The total cost is O(n) + O(n)*O(9) = O(n).

How does the algorithm work on the examples:

93561 ->   it can swap in the first cycle  596   ->   skipping the first cycle,             then finds '6' because of the position constraint             (comparing position '1' with last[5] = 0, last[6] = 2)  10234 ->   does not find anything because of the position constraint  93218910471211292416 -> finds the last occurrence of '1' to replace '9'  98761111 -> it can swap in the first cycle             (last[1] = 7, so it will change the last occurrence)  555555555555555555596 -> iterates until the '9', then you skip last[5]             but finds last[6] as a good swap  120 ->      at pos 0 (1) cannot find a non-zero element less than 1, so skip             at pos 1 (2) can find 0 on position 2, so we swap 

Once again, here we do one iteration on the digits (for pre-parsing the data), then one iteration for finding the MSB. In the second iteration we iterate on last, which is constant size (at most 9).

You can further optimize the algorithm by adding keeping track of the minimum value when it is worth to start the loop on last, but that's an optimization already. The prevoius version contained that, check the history if you're interested :)