A recent post on SO has presented this challenge:
Q: Given a positive integer, you are allowed to perform 1 swap to return the smallest possible result. Leading zeros are not allowed.
This question has received quite a lot of attention of SO, as people try to come up with an algorithm with linear runtime. So I thought I would have a crack. Coming up with an algorithm that runs in O(n) is simple enough. My python version is below:
This meets all the targets – it runs in linear time, looping through the array once before performing a swap. However it is nagging at me though, there must be a more elegant solution than this. It is close to a sorting algorithm, so perhaps I can use a divide-and-conquer approach, recursion, list-comprehension even?
The first step will be to make a general sorting algorithm I think. Nothing fancy, perhaps it will inspire me to a more imaginative solution for this question. Watch for follow up blogs…