LeetCode 556: Next Greater Element III

Explanation

To find the next greater element that can be formed by rearranging the digits of a given number n, we can start from the rightmost digit and compare it with the digits to its left. We want to find the first digit from the right that is smaller than any digit to its right. Once we find such a digit, we swap it with the smallest digit to its right that is greater than it. Then, we sort the digits to the right of the swapped digit in ascending order to get the smallest possible number greater than the original number.

Algorithm

1. Convert the integer n to a character array to work with individual digits.
2. Start from the rightmost digit and find the first digit (let's call it i) that is smaller than the digit to its right (let's call it j).
3. If no such digit i exists, it means the number is already the largest possible number with the given digits. Return -1.
4. Find the smallest digit that is greater than digit i to the right of digit i. Swap digit i with this smallest digit.
5. Sort all digits to the right of digit i in ascending order to get the smallest number possible.
6. Convert the modified character array back to an integer and check if it exceeds the 32-bit integer limit. Return -1 if it does.
7. Otherwise, return the new integer as the answer.

Time Complexity

The time complexity of this algorithm is O(n) where n is the number of digits in the input number n.

Space Complexity

The space complexity of this algorithm is O(n) for storing the character array representation of the input number.

class Solution {
    public int nextGreaterElement(int n) {
        char[] digits = String.valueOf(n).toCharArray();
        
        int i = digits.length - 2;
        while (i >= 0 && digits[i] >= digits[i + 1]) {
            i--;
        }
        
        if (i == -1) {
            return -1;
        }
        
        int j = digits.length - 1;
        while (j >= 0 && digits[j] <= digits[i]) {
            j--;
        }
        
        swap(digits, i, j);
        reverse(digits, i + 1, digits.length - 1);
        
        long result = Long.parseLong(new String(digits));
        return (result > Integer.MAX_VALUE) ? -1 : (int) result;
    }
    
    private void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    private void reverse(char[] arr, int start, int end) {
        while (start < end) {
            swap(arr, start, end);
            start++;
            end--;
        }
    }
}