59. Next Greater Number With the Same Set of Digits

Given a number as a string of digits, find the smallest number greater than it that can be formed using exactly the same digits. If no such number exists, print -1.

Input: The input is a single line containing the number as a string of digits. Output: Print the smallest number greater than the input using exactly the same digits, or print -1 if none exists.

1 <= number of digits <= 10^5

The segment after the pivot is always in strictly DECREASING order before the swap (a direct consequence of how the pivot is defined) - which is exactly why reversing it (rather than fully re-sorting) is sufficient and slightly more efficient.

Given a number, rearrange its digits to form the smallest possible number that's still bigger than the original, using exactly the same digits. Brute force: Generate every possible permutation of the digits, sort them all, and find the one immediately after the current number - this is factorial time, completely impractical for even moderately long digit strings. Optimised: This is exactly the 'Next Permutation' technique (pivot-find, smallest-larger-swap, reverse/sort the tail) applied directly to digits instead of general array elements - the same O(n) construction, no permutation generation needed at all.

Generate every distinct permutation of the given digits, convert each to its numeric value, and pick the smallest one that is strictly greater than the original number. This tries all rearrangements exhaustively and is correct, but factorial in the number of digits, only usable for very short digit strings. Time: O(d! * d) Space: O(d)

Scan from the rightmost digit to find the first position i (from the right) where digit[i] is smaller than the digit immediately to its right; everything to the right of i is already in non-increasing order. Scan that suffix to find the smallest digit still larger than digit[i], swap it into position i, and then fully sort the remaining suffix into ascending order to make it as small as possible. Sorting the suffix explicitly, rather than exploiting its known structure, adds a logarithmic factor over its size. Time: O(n log n) Space: O(n)

Find the pivot index i, scanning from the right, where digit[i] < digit[i+1], noting that everything after i is currently sorted in non-increasing order. Scan again from the right to find the smallest digit greater than digit[i] within that suffix (guaranteed to exist by the pivot's definition) and swap it with digit[i]. Since the suffix after the swap remains non-increasing, simply reverse it in place to turn it into ascending order, the smallest possible completion, without any general-purpose sort; if no pivot exists at all, the digits are already the largest possible arrangement, so print -1. Time: O(n) Space: O(1)

1. Scan from the right end looking for the first position where a digit is SMALLER than the digit right after it (the 'pivot'). 2. If no such position exists, the digits are already in the largest possible arrangement - no bigger number exists. 3. Otherwise, scan from the right again to find the smallest digit still LARGER than the pivot, and swap it with the pivot. 4. Sort everything after the pivot's position in ascending order, giving the smallest possible increase.

Time: O(n) - the pivot search, swap-candidate search, and tail sort are each linear (or near-linear, since the tail is already known to be in decreasing order before the swap, making a reverse sufficient instead of a full sort). Space: O(n), for the digit array representation (or O(1) extra if manipulating the digit string in place).

Digits already arranged in descending order, meaning no greater arrangement exists (-1); repeated digits requiring careful tie-breaking when picking the smallest larger digit to swap; up to 10^5 digits, testing performance of the suffix scan.

Be ready to connect this immediately to the general 'Next Permutation' array problem - recognizing that a specific-looking problem is really a familiar general technique in disguise is exactly the kind of pattern-matching interviewers look for.