556. Next Greater Element III

#pivot #next-greater #permutation

Problem

Next Greater Element III - LeetCodeLeetCode

Intuition

Permutation

Time Complexity

O(n)[find pivot element]

+ O(n-j)[next greater element]

+ O((n-i) log(n-1)) [sorting]

Overall it is O(n)

Space Complexity

O(n), for converting integer to char array

Solution

class Solution {
    public int nextGreaterElement(int n) {
        // Time Complexity:
        // O(n)[find pivot element] + O(n-j)[next greater element]
        // + O((n-i) log(n-1)) [sorting]
        // Overall it is O(n)
        // Space complexity: O(n), for converting integer to char array


        // Convert the given number to a character array
        char[] nCharArr = String.valueOf(n).toCharArray();

        // Find the first pivot element from right to left
        int i = nCharArr.length - 2;
        for (; i >= 0; i--) {
            if (nCharArr[i] < nCharArr[i + 1]) {
                break;
            }
        }

        // If no pivot element is found, return -1
        if (i < 0) {
            return -1;
        }

        // Find the next greater element from the right side of the pivot
        int j = nCharArr.length - 1;
        while (j >= 0 && nCharArr[j] <= nCharArr[i]) {
            j--;
        }

        // Swap the pivot element with the next greater element
        char temp = nCharArr[i];
        nCharArr[i] = nCharArr[j];
        nCharArr[j] = temp;

        // Sort the remaining elements in non-decreasing order
        Arrays.sort(nCharArr, i + 1, nCharArr.length);

        try {
            // Convert the character array back to an integer
            return Integer.parseInt(new String(nCharArr));
        } catch (Exception e) {
            // Return -1 in case of any exception during parsing
            return -1;
        }
    }
}