# 0556. Next Greater Element III

https://leetcode.com/problems/next-greater-element-iii

## Description

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`

## ac

so many anoying boundary check

```java
class Solution {
    public int nextGreaterElement(int n) {
        // edge cases
        if (n <= 10) return -1;

        List<Integer> list = new ArrayList<>();
        int exchange = -1;
        while (n > 0) {
            int curr = n % 10;
            n /= 10;
            if (list.size() != 0 && curr < list.get(list.size() - 1)) {
                int i = list.size() - 1;
                while (i >= 0 && curr < list.get(i)) i--;
                exchange = list.get(i+1);
                list.set(i+1, curr);
                break;
            } else {
                list.add(curr);
            }
        }

        if (n == 0 && exchange == -1) return -1;  // cannot find result

        n = n * 10 + exchange;
        for (int i : list) {
            if (n > Integer.MAX_VALUE / 10 || n == Integer.MAX_VALUE / 10 && i > 8) 
                return -1;  // out of boundary
            n = n * 10 + i;
        }

        return n;
    }
}
```

```java
class Solution {
    public int nextGreaterElement(int n) {
        // edge cases
        if (n <= 10) return -1;

        // 1) walk backwardly, when the digit is ascending add to list, when meet smaller digit, it's swap point;
        List<Integer> list = new ArrayList<>();
        while (n > 0) {
            int curr = n % 10;
            n /= 10;
            if (list.size() == 0 || curr >= list.get(list.size() - 1)) {
                list.add(curr);
            } else { // found swap point, find greater digit
                int i = list.size() - 1;
                while (i >= 1 && curr < list.get(i-1)) i--;
                int tmp = list.get(i);
                list.set(i, curr);
                n = n * 10 + tmp;
                break;
            }
        }

        if (n == 0) return -1; // all digits ascending, no swap

        long res = n;
        for (int d : list) {
            res = res * 10 + d;
        }

        if (res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) return -1;
        else return (int) res;
    }
}

/*
1) walk backwardly, when the digit is ascending add to list, when meet smaller digit, it's swap point; 2) iterate the list to find the smallest digit greater than current one, swap then; 3) get the rest from list, it's in ascending order.
*/
```
