# 556. Next Greater Element III

## Problem

{% embed url="<https://leetcode.com/problems/next-greater-element-iii/description/>" %}

## Intuition

{% content-ref url="../arrays-and-strings/permutation" %}
[permutation](https://chkrishnatej.gitbook.io/interview-prep/arrays-and-strings/permutation)
{% endcontent-ref %}

## Time Complexity

{% hint style="info" %}
&#x20; O(n)\[find pivot element]

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

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

Overall it is **O(n)**
{% endhint %}

## Space Complexity

{% hint style="success" %}
**O(n)**, for converting integer to char array
{% endhint %}

## Solution

```java
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;
        }
    }
}
```