556. Next Greater Element III

/*
Very similar to: https://leetcode.com/problems/next-permutation/
Refer: https://leetcode.com/submissions/detail/176366402/

Time Complexity: O(N)
Space Complexity: O(N)

N = number of digits in n... its max 10 (Integer Max).
Thus, time complexity can be O(1) and space complexity can be O(1).
*/
class Solution {
    public int nextGreaterElement(int n) {
        if (n < 12) {
            return -1;
        }

        // Converting digits of n into character array.
        char[] numChar = String.valueOf(n).toCharArray();


        // Starting from right side, find the first digit that is smaller to its right neighbour.
        int i = numChar.length - 1;
        while (i > 0 && numChar[i-1] >= numChar[i]) {
            i--;
        }

        if (i == 0) {
            return -1;
        }

        // For the previous found digit, find the next greater digit on the right and swap them.
        int j = numChar.length - 1;
        while (j >= i && numChar[j] <= numChar[i-1]) {
            j--;
        }
        swap(numChar, i-1, j);

        // Reverse all the digits before the (i-1) digit.
        // (No need to sort as all the digits on right are sorted in descending order).
        reverse(numChar, i);

        try {
            return Integer.parseInt(new String(numChar));
        } catch (Exception e) {
            return -1;
        }
    }

    private void reverse(char[] charArr, int start) {
        int end = charArr.length - 1;
        while (start < end) {
            swap(charArr, start, end);
            start++;
            end--;
        }
    }

    private void swap(char[] charArr, int i, int j) {
        char temp = charArr[i];
        charArr[i] = charArr[j];
        charArr[j] = temp;
    }
}