# Next Greater Element III
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/next-greater-element-iii)
Canonical: https://scaleengineer.com/dsa/problems/next-greater-element-iii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Mitsogo](https://scaleengineer.com/companies/mitsogo)
---
## Problem
Given a positive integer `n`, find _the smallest integer which has exactly the same digits existing in the integer_ `n` _and is greater in value than_ `n`. If no such positive integer exists, return `-1`.

**Note** that the returned integer should fit in **32-bit integer**, if there is a valid answer but it does not fit in **32-bit integer**, return `-1`.

**Example 1:**

**Input:** n = 12
**Output:** 21

**Example 2:**

**Input:** n = 21
**Output:** -1

**Constraints:**

* `1 <= n <= 231 - 1`

# Approaches
## Brute-Force by Generating All Permutations
This approach tackles the problem by generating all possible numbers that can be formed by rearranging the digits of the input number `n`. From this complete set of permutations, we filter to find all numbers that are strictly greater than `n`. The smallest number in this filtered set is our answer. If no such number exists, it means `n` is already the largest possible permutation of its digits.
**Time:** O(d! * d), where `d` is the number of digits in `n`. For a 32-bit integer, `d` is at most 10. Generating `d!` permutations and converting each to a number of length `d` leads to this complexity. · **Space:** O(d! * d). We need to store up to `d!` permutations, each requiring `O(d)` space.
**Pros:** Conceptually simple and directly follows the problem's definition of rearranging digits.; Guaranteed to find the correct answer if one exists (within computational limits).
**Cons:** Extremely inefficient due to factorial time complexity. Unsuitable for numbers with more than a few digits.; High memory consumption to store all generated permutations.
### Explanation
The core of this method is a permutation generation algorithm. We first convert the integer `n` into an array of its digits. Then, we use a recursive function, typically employing backtracking, to generate every unique arrangement of these digits. Each permutation is converted back into a number. We maintain a list of all generated numbers that are larger than the original `n`. After exploring all permutations, we find the minimum value in this list. A special check is required to ensure the result does not exceed the 32-bit integer limit. If no greater number is found, or the smallest greater number overflows, we return -1.
```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public int nextGreaterElement(int n) {
        String s = String.valueOf(n);
        char[] digits = s.toCharArray();
        Set<Long> permutations = new HashSet<>();
        // Using a Set helps handle duplicate permutations automatically
        generatePermutations(digits, 0, permutations);

        long minGreater = Long.MAX_VALUE;
        boolean found = false;

        for (long p : permutations) {
            if (p > n) {
                minGreater = Math.min(minGreater, p);
                found = true;
            }
        }

        if (!found || minGreater > Integer.MAX_VALUE) {
            return -1;
        }

        return (int) minGreater;
    }

    private void generatePermutations(char[] digits, int index, Set<Long> permutations) {
        if (index == digits.length) {
            try {
                permutations.add(Long.parseLong(new String(digits)));
            } catch (NumberFormatException e) {
                // This case is unlikely given the constraints but good practice.
            }
            return;
        }

        // Generate permutations for the rest of the array
        for (int i = index; i < digits.length; i++) {
            swap(digits, index, i);
            generatePermutations(digits, index + 1, permutations);
            swap(digits, index, i); // backtrack
        }
    }

    private void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
```
### Algorithm
- Convert the input integer `n` into a character array representing its digits.
- Define a recursive function to generate all permutations of the digits. Use a `Set` to store the unique numbers formed by these permutations to avoid duplicates.
- In the recursive function:
  - Base case: When a full permutation is formed (i.e., we've reached the end of the digit array), convert it to a `long` and add it to the set.
  - Recursive step: Iterate through the remaining digits, swap the current digit with each of the others, and make a recursive call.
- After generating all permutations, iterate through the set of numbers.
- Find the minimum number that is greater than the original `n`.
- If no such number is found, or if the found number is larger than `Integer.MAX_VALUE`, return -1.
- Otherwise, return the found number as an `int`.

## Optimal Single-Pass Approach (Next Permutation)
A highly efficient approach that avoids generating all permutations. It's based on the standard algorithm for finding the next lexicographically greater permutation of a sequence. By making a few targeted modifications to the sequence of digits, we can directly construct the smallest number that is larger than the input `n`.
**Time:** O(d), where `d` is the number of digits in `n`. The algorithm involves a few linear scans of the digit array, each taking `O(d)` time. · **Space:** O(d) to store the digits of the number in a character array.
**Pros:** Extremely efficient, with a time complexity linear in the number of digits.; Minimal space usage.; Directly constructs the answer without generating unnecessary permutations.
**Cons:** The logic can be non-obvious and requires understanding the properties of lexicographical permutations.
### Explanation
The algorithm works by manipulating the digits of `n` as a character array. We scan the digits from right to left to find the first position `i` where the digit is smaller than the digit to its right (`a[i] < a[i+1]`). This digit `a[i]` is our 'pivot'. The suffix of the number starting from `i+1` is in non-increasing (descending) order.
Next, we find the smallest digit in this suffix that is still larger than our pivot `a[i]`. We swap this digit with the pivot.
Finally, to ensure the resulting number is the *smallest* possible greater number, we reverse the suffix that starts after the pivot's original position. This arranges the remaining digits in ascending order. The resulting sequence of digits forms our answer, which we convert back to a number, checking for 32-bit integer overflow.
```java
import java.util.Arrays;

class Solution {
    public int nextGreaterElement(int n) {
        char[] a = String.valueOf(n).toCharArray();
        int len = a.length;
        int i = len - 2;
        
        // Step 1: Find the first digit from the right that is smaller than the digit to its right.
        while (i >= 0 && a[i] >= a[i+1]) {
            i--;
        }
        
        // If no such digit is found, it means the digits are in descending order (e.g., 321).
        // This is the largest permutation, so no greater element exists.
        if (i < 0) {
            return -1;
        }
        
        // Step 2: Find the smallest digit to the right of a[i] that is greater than a[i].
        int j = len - 1;
        while (j > i && a[j] <= a[i]) {
            j--;
        }
        
        // Step 3: Swap the pivot a[i] with a[j].
        swap(a, i, j);
        
        // Step 4: Reverse the part of the array to the right of i to get the smallest permutation.
        reverse(a, i + 1);
        
        try {
            long val = Long.parseLong(new String(a));
            if (val > Integer.MAX_VALUE) {
                return -1;
            }
            return (int) val;
        } catch (NumberFormatException e) {
            // This catch block handles cases where the number is too large for a long,
            // which is not possible given the constraints on n, but is good practice.
            return -1;
        }
    }
    
    private void swap(char[] a, int i, int j) {
        char temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    private void reverse(char[] a, int start) {
        int i = start, j = a.length - 1;
        while (i < j) {
            swap(a, i, j);
            i++;
            j--;
        }
    }
}
```
### Algorithm
- Convert the input integer `n` to a character array `a`.
- Scan `a` from right to left to find the first index `i` such that `a[i] < a[i+1]`. This is the pivot.
- If no such `i` exists, all digits are in descending order. Return -1.
- Scan `a` again from right to left (from the end to `i+1`) to find the first index `j` where `a[j] > a[i]`.
- Swap the characters at indices `i` and `j`.
- Reverse the subarray of `a` from index `i+1` to the end.
- Convert the modified character array `a` back to a number. Use `long` to prevent premature overflow during parsing.
- Check if the resulting number exceeds `Integer.MAX_VALUE`. If it does, return -1. Otherwise, cast to `int` and return.

# Solutions
### Java

```java
class Solution {
public
  int nextGreaterElement(int n) {
    char[] cs = String.valueOf(n).toCharArray();
    n = cs.length;
    int i = n - 2, j = n - 1;
    for (; i >= 0 && cs[i] >= cs[i + 1]; --i)
      ;
    if (i < 0) {
      return -1;
    }
    for (; cs[i] >= cs[j]; --j)
      ;
    swap(cs, i, j);
    reverse(cs, i + 1, n - 1);
    long ans = Long.parseLong(String.valueOf(cs));
    return ans > Integer.MAX_VALUE ? -1 : (int)ans;
  }
private
  void swap(char[] cs, int i, int j) {
    char t = cs[i];
    cs[i] = cs[j];
    cs[j] = t;
  }
private
  void reverse(char[] cs, int i, int j) {
    for (; i < j; ++i, --j) {
      swap(cs, i, j);
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int nextGreaterElement(int n) {
    string s = to_string(n);
    n = s.size();
    int i = n - 2, j = n - 1;
    for (; i >= 0 && s[i] >= s[i + 1]; --i)
      ;
    if (i < 0)
      return -1;
    for (; s[i] >= s[j]; --j)
      ;
    swap(s[i], s[j]);
    reverse(s.begin() + i + 1, s.end());
    long ans = stol(s);
    return ans > INT_MAX ? -1 : ans;
  }
};

```

### Python

```python
class Solution:
    def nextGreaterElement(self, n: int) -> int: cs = list(str(n)) n = len(cs) i, j = n - 2, n - 1 while i >= 0 and cs[i] >= cs[i + 1]: i -= 1 if i < 0: return - 1 while cs[i] >= cs[j]: j -= 1 cs[i], cs[j] = cs[j], cs[i] cs[i + 1:] = cs[i + 1:][:: - 1] ans = int('' . join(cs)) return - 1 if ans > 2 ** 31 - 1 else ans

```