Leetcode 556. Next Greater Element III

Problem

Given a positive integer n, find the smallest integer that is greater than n and contains exactly the same digits as n. In other words, find the next lexicographic permutation of the digits in n.

If no such integer exists (because n is already the largest permutation of its digits), or if the result would exceed the 32-bit signed integer maximum value (2³¹ - 1 = 2,147,483,647), return -1.

Requirements

1. The result must use exactly the same digits as the input number
2. The result must be the smallest number greater than the input
3. Return -1 if no valid permutation exists
4. Return -1 if the result exceeds 2,147,483,647

Constraints

• 1 ≤ n ≤ 2³¹ - 1
• The solution should run in O(d) time where d is the number of digits
• Space complexity should be O(d) for storing digits

Examples

Example 1:

Input: n = 12 Output: 21 Explanation: The only greater permutation of digits 1 and 2 is 21.

Example 2:

Input: n = 230241 Output: 230412 Explanation: Starting from the right, we find that 2 (at position 3 from left) is the first digit smaller than its successor. We swap it with 4 (the smallest digit greater than 2 in the suffix), giving 230421. Then we reverse the suffix after position 3 to get 230412.

Example 3:

Input: n = 321 Output: -1 Explanation: The digits are in descending order, so this is already the largest permutation possible.

Example 4:

Input: n = 1 Output: -1 Explanation: A single digit has no other permutation.

Hint 1: Finding the Pivot To find the next permutation, scan from right to left to find the first digit that is smaller than the digit to its right. This is your "pivot" position. If no such digit exists, the number is already at its maximum permutation.

Hint 2: Swapping Strategy Once you've found the pivot, you need to swap it with the smallest digit to its right that is still larger than the pivot. After swapping, the suffix to the right of the pivot position should be arranged in ascending order to ensure the result is the smallest possible greater number.

Hint 3: Optimization After swapping, notice that the suffix is still in descending order (because we found the rightmost position to swap). You can simply reverse this suffix instead of sorting it, which takes O(d) time instead of O(d log d).

Full Solution `` Explanation:

The algorithm implements the standard next permutation procedure:

1. Find the pivot: Scan from right to left to find the first position where a digit is smaller than its right neighbor. This marks the position where we need to make a change. If no such position exists, the digits are in descending order and we're already at the maximum permutation.
2. Find the swap candidate: Among all digits to the right of the pivot, find the smallest one that is still larger than the pivot digit. Due to the descending order of the suffix, this is simply the rightmost digit greater than the pivot.
3. Swap: Exchange the pivot with the swap candidate.
4. Minimize the suffix: After swapping, the suffix (everything after the pivot position) is still in descending order. Reverse it to make it ascending, which gives us the smallest possible arrangement.
5. Boundary check: Verify the result doesn't exceed the 32-bit integer limit.

Time Complexity: O(d) where d is the number of digits in n. We make at most three passes through the digits.

Space Complexity: O(d) for storing the digit array.