You can do it in `O(n)`

(where `n`

is the number of digits) like this:

Starting from the right, you find the first pair-of-digits such that the left-digit is smaller than the right-digit. Let's refer to the left-digit by "digit-x". Find the smallest number larger than digit-x to the right of digit-x, and place it immediately left of digit-x. Finally, sort the remaining digits in ascending order - since they were already in *descending* order, all you need to do is reverse them *(save for digit-x, which can be placed in the correct place in *`O(n)`

).

An example will make this more clear:

123456784987654321
start with a number
123456784 987654321
^the first place from the right where the left-digit is less than the right
Digit "x" is 4
123456784 987654321
^find the smallest digit larger than 4 to the right
123456785 4 98764321
^place it to the left of 4
123456785 4 12346789
123456785123446789
^sort the digits to the right of 5. Since all of them except
the '4' were already in descending order, all we need to do is
reverse their order, and find the correct place for the '4'

**Proof of correctness:**

Let's use capital letters to define digit-strings and lower-case for digits. The syntax `AB`

means *"the concatenation of strings *`A`

and `B`

". `<`

is lexicographical ordering, which is the same as integer ordering when the digit-strings are of equal length.

Our original number N is of the form `AxB`

, where `x`

is a single digit and `B`

is sorted descending.

The number found by our algorithm is `AyC`

, where `y ∈ B`

is the smallest digit `> x`

*(it must exist due to the way *`x`

was chosen, see above), and `C`

is sorted ascending.

Assume there is some number (using the same digits) `N'`

such that `AxB < N' < AyC`

. `N'`

must begin with `A`

or else it could not fall between them, so we can write it in the form `AzD`

. Now our inequality is `AxB < AzD < AyC`

, which is equivalent to `xB < zD < yC`

where all three digit-strings contain the same digits.

In order for that to be true, we must have `x <= z <= y`

. Since `y`

is the smallest digit `> x`

, `z`

cannot be between them, so either `z = x`

or `z = y`

. Say `z = x`

. Then our inequality is `xB < xD < yC`

, which means `B < D`

where both `B`

and `D`

have the same digits. However, B is sorted descending, so there *is* no string with those digits larger than it. Thus we cannot have `B < D`

. Following the same steps, we see that if `z = y`

, we cannot have `D < C`

.

Therefore `N'`

cannot exist, which means our algorithm correctly finds the next largest number.

a start at leastwould be brute force calculate all permutations of the digits and grab the minimum number that is larger than the input number`next_permutation`

;-)thatdata until a pattern emerged from the list (the O(n) accepted solution here became clear after just a short time looking), then I spent 5 minutes coding the O(n) algorithm.reallycan't figure out an efficient way to do this, doing nothing is sure way to fail the interview (and in the business world, it's a sure way to miss a product deadline). When you got stuck, instead of giving up, you should have just brute forced it and put a comment on the top "TODO: refactor for performance" or something like that. If I was interviewing and someone did that, I wouldn't necessarily fail them. At least they came up withsomething that workedAND recognized that something better was out there, even if they couldn't find it.4more comments