# Swap only two digits resulting in a minimum number

An interesting algorithmic question:

“Given a string of digits 0-9, swap only two digits such that it produces the smallest number possible with the restriction that you can not have leading zeros in the number. For example, 101, can not be swapped into 011.

The simple approach would be O(k^2), where k is the number of digits in the string. The algorithm I posted below runs in worst case O((radix+1)*k) – linear by length of input with a constant of the radix plus the scan to find the rightmost index of each number.

Advertisements

Leave a Comment