For this question you can keep an array of 0-9

Start traversing from back, if any bucket before that is fill that is you encountered an element smaller than it then put that element in current position and place all remaning elements in decreasing order.

For example say the no is 10987598023

start from 3

A = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

array after 3 becomes [0, 0, 0, 1, 0,..]

then when u see 2, you see that no smaller element. Array becomes

[0, 0, 1, 1, 0,...]

now when u reach at 0, again no smaller element, so array becomes

[1, 0, 1, 1, 0, ...]

Now when u reach 8 the just smaller element is 3

So, replace 8 with 3 and the array becomes [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0]

So the number just smaller is 10987593820. O(n)

I gave the obvious solution of generating all permutations of the number n and ordering them, find the one that occurs before n.

Then I figured out that if I sort the digits from a certain point onwards into increasing order, it can help me build up to the solution. I proposed my algorithm and we began doing some really sort of pseudofunctional java code that solved the problem. After the end of that, I analyzed my solution and found it to run in O(n^2) time utilizing a bucket sort for the sorting operation. This was a big improvement from O(n!) but still not optimum. He explained the optimum solution found a pivot at which point it sorted the digits, running in O(n).