Next Greater Element III

Problem Statement

Given a positive integer n, the objective is to determine the smallest integer that comprises exactly the same digits as n but has a greater numerical value. If such an integer does not exist, the function should return -1. An additional condition is that the resultant integer should fit within a standard 32-bit integer range. If a potential solution exists but it exceeds the maximum value that a 32-bit integer can hold (i.e., it doesn't fit within the 32-bit integer range), the function should also return -1. This problem is a classic next permutation problem with the additional constraint of the 32-bit integer limitation.

Examples

Example 1

Input:

n = 12

Output:

21

Example 2

Input:

n = 21

Output:

-1

Constraints

• 1 <= n <= 231 - 1

Approach and Intuition

To solve this problem, we can utilize the concept of finding the next lexicographical permutation of the digits:

1. Identify the rightmost digit that is smaller than the digit immediately to its right. This digit is termed as the 'pivot'.
2. If such a pivot does not exist, this indicates that we are dealing with the highest permutation of these digits, and therefore, a return value of -1 is appropriate.
3. If a pivot is found, the next step is to locate the smallest digit on the right side of the pivot that is larger than the pivot itself because swapping these will guarantee the next smallest configuration.
4. Swap the pivot with this chosen digit.
5. Finally, to ensure that the resulting number is the smallest possible number larger than n, the digits to the right of the original pivot should be reversed (since they were originally in descending order to make the largest number possible with those digits).

By following these steps, the number generated will have the same digits as n and will be the immediate next larger number. After generating this next permutation, a final check is necessary to ensure the result can be represented as a 32-bit integer. If the resulting integer exceeds the 32-bit integer maximum value, then return -1, otherwise, return the new integer.

Key Considerations

• The approach hinges on finding the correct pivot and then correctly identifying the smallest larger digit to create the next permutation.
• Ensuring the result fits within a 32-bit integer is critical and must be checked after determining the next permutation.

With these steps and considerations, the problem can be efficiently and effectively addressed within the given constraints.

Solutions

public class Solution {
    public int findNextGreater(int number) {
        char[] digits = Integer.toString(number).toCharArray();
        int index = digits.length - 2;
        while (index >= 0 && digits[index + 1] <= digits[index]) {
            index--;
        }
        if (index < 0)
            return -1;
        int swapIndex = digits.length - 1;
        while (swapIndex >= 0 && digits[swapIndex] <= digits[index]) {
            swapIndex--;
        }
        exchange(digits, index, swapIndex);
        reversePortion(digits, index + 1);
        try {
            return Integer.parseInt(new String(digits));
        } catch (Exception ex) {
            return -1;
        }
    }
    private void reversePortion(char[] array, int begin) {
        int left = begin, right = array.length - 1;
        while (left < right) {
            exchange(array, left, right);
            left++;
            right--;
        }
    }
    private void exchange(char[] array, int x, int y) {
        char t = array[x];
        array[x] = array[y];
        array[y] = t;
    }
}