Finding the Next Largest Number

with the same set of digits

An Algorithm

Problem Statement: Given a number, find the next higher number which has the exact same set of digits as the original number. For example: Given 545543, return 553445.

Analysis: The most brute force way to solve this is to calculate all permutations of the digits present, sort them, and then compare the original number against each until the first one that is larger is reached. The time complexity here is insane. O(n *n!). And that's not counting the sort.

Solution: There is actually an O(n) solution to this, just takes a little human ingenuity. The idea here is that given 545543, no matter how much jumbling we do to the ending -5543, we will not produce a larger number.

In this case, we know that the ten-thousands position is the determining place value that will vary in the solution. We replace the 4 currently there with the smallest number that comes after it that is also larger than it, 5. Because 55xxxx will always be greater than 54xxxx, and we are calculating the next highest, we sort the ending digits in ascending order thus giving us the smallest valued variant of the ending digits.

Ruby-ized:

Checking for the place value: O(n). Sort: Will always be O(n) in this case.

Happy coding.