414. Next Greater Element III
You are given a positive integer n. Rearrange its digits to build a new integer that is strictly greater than n, using every digit exactly once — and among all such rearrangements, pick the smallest one.
Your function receives the integer n and returns that smallest greater rearrangement. If no rearrangement of the digits is greater than n, or if the smallest greater one does not fit in a signed 32-bit integer (that is, it exceeds 2^31 - 1 = 2147483647), return -1 instead.
Example 1:
Input: n = 12
Output: 21
Explanation: The only other arrangement of the digits 1 and 2 is 21, and it is greater than 12.
Example 2:
Input: n = 21
Output: -1
Explanation: The digits 2 and 1 are already in descending order — 21 is the largest number they can spell, so nothing greater exists.
Example 3:
Input: n = 230241
Output: 230412
Explanation: Keeping the prefix 230 and rearranging the tail 241 gives 230412, the smallest arrangement that beats 230241.
Constraints:
- 1 ≤ n ≤ 2³¹ - 1
- The answer must also fit in a signed 32-bit integer, otherwise return -1.
Hints:
Work on the digit string. To make the number bigger by as little as possible, you want to keep the longest possible prefix untouched and fix things as far to the right as you can.
Scan from the right for the first digit that is smaller than the digit after it (the pivot). Everything right of the pivot is non-increasing — swap the pivot with the smallest digit to its right that still beats it, then sort the tail ascending. Because the tail was non-increasing, sorting it is just reversing it (two pointers).
Do the final size check with 64-bit math or a string comparison: the rearrangement of a 10-digit n can exceed 2^31 - 1 even though n itself fits.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 12
Expected output: 21