## Algorithm

Problem Name: 556. Next Greater Element III

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`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int nextGreaterElement(int n) {
string s = to_string(n);
stack < char>q;
stack<int>idx;
for (int i = s.size() - 1; i >= 0; --i) {
if (q.empty() || q.top()  < = s[i]) {
q.push(s[i]);
idx.push(i);
} else {
int pos = -1;
while (!q.empty() && q.top() > s[i]) {
pos = idx.top();
q.pop();
idx.pop();
}
swap(s[i], s[pos]);
sort(s.begin() + i + 1, s.end());
long l = stol(s);
if (l > INT_MAX) return -1;
return l;
}
}
return -1;
}
};

class Solution {
public:
int nextGreaterElement(int n) {
string s = to_string(n);
next_permutation(s.begin(), s.end());
auto res = stol(s);
return (res > INT_MAX || res  < = n) ? -1 : res;
return -1;
}
};
``````
Copy The Code &

Input

cmd
n = 12

Output

cmd
21

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int nextGreaterElement(int n) {
char[] digits = String.valueOf(n).toCharArray();
int idx = digits.length - 2;
while (idx >= 0) {
if (Character.getNumericValue(digits[idx])  <  Character.getNumericValue(digits[idx + 1])) {
int secondIdx = digits.length - 1;
while (secondIdx >= idx && digits[secondIdx] <= digits[idx]) {
secondIdx--;
}
swap(digits, idx, secondIdx);
int start = idx + 1;
int end = digits.length - 1;
while (start  <  end) {
swap(digits, start++, end--);
}
try {
return Integer.parseInt(new String(digits));
} catch (Exception e) {
return -1;
}
}
idx--;
}
return -1;
}

private void swap(char[] digits, int idxOne, int idxTwo) {
char temp = digits[idxOne];
digits[idxOne] = digits[idxTwo];
digits[idxTwo] = temp;
}
}
``````
Copy The Code &

Input

cmd
n = 12

Output

cmd
21

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const nextGreaterElement = function(n) {
let i, j;
const arr = (n + "").split("").map(el => +el);
for (i = arr.length - 2; i >= 0; i--) {
if (arr[i]  <  arr[i + 1]) {
break;
}
}
if (i < 0) return -1;
j = arr.length - 1;
while (arr[j]  < = arr[i]) {
j--;
}
swap(arr, i, j);
reverse(arr, i + 1, arr.length - 1);

const res = arr.reduce((ac, el) => ac + el, "");
return res > Math.pow(2, 31) - 1 ? -1 : +res
};

function swap(arr, i, j) {
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
}

function reverse(arr, start, end) {
let l = start;
let h = end;
while (l  <  h) {
swap(arr, l++, h--);
}
}
``````
Copy The Code &

Input

cmd
n = 21

Output

cmd
-1

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def nextGreaterElement(self, n):
arr = [c for c in str(n)]
for l in range(len(arr) - 2, -1, -1):
r = len(arr) - 1
while l < r and arr[r] <= arr[l]:
r -= 1
if l != r:
arr[l], arr[r] = arr[r], arr[l]
arr[l + 1:] = sorted(arr[l + 1:])
num = int("".join(arr))
return num if -2 ** 31 <= num <= 2 ** 31 - 1 else -1
return -1
``````
Copy The Code &

Input

cmd
n = 21

Output

cmd
-1