• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
int nextGreaterElement(int n) {
const string& s = nextPermutation(to_string(n));
const long ans = stol(s);
return ans > INT_MAX || ans <= n ? -1 : ans;
}

private:
// very similar to 31. Next Permutation
string nextPermutation(string s) {
const int n = s.length();

int i;
for (i = n - 2; i >= 0; --i)
if (s[i] < s[i + 1])
break;

if (i >= 0) {
for (int j = n - 1; j > i; --j)
if (s[j] > s[i]) {
swap(s[i], s[j]);
break;
}
}

reverse(s, i + 1, n - 1);
return s;
}

void reverse(string& s, int l, int r) {
while (l < r)
swap(s[l++], s[r--]);
}
};
``````

## JAVA

``````class Solution {
public int nextGreaterElement(int n) {
final String s = nextPermutation(String.valueOf(n).toCharArray());
final long ans = Long.parseLong(s);
return ans > Integer.MAX_VALUE || ans <= (long) n ? -1 : (int) ans;
}

// very similar to 31. Next Permutation
private String nextPermutation(char[] s) {
final int n = s.length;

int i;
for (i = n - 2; i >= 0; --i)
if (s[i] < s[i + 1])
break;

if (i >= 0) {
for (int j = n - 1; j > i; --j)
if (s[j] > s[i]) {
swap(s, i, j);
break;
}
}

reverse(s, i + 1, n - 1);
return new String(s);
}

private void reverse(char[] s, int l, int r) {
while (l < r)
swap(s, l++, r--);
}

private void swap(char[] s, int i, int j) {
final char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}
``````

## Python

``````class Solution:
def nextGreaterElement(self, n: int) -> int:
def nextPermutation(s: List[chr]) -> str:
i = len(s) - 2
while i >= 0:
if s[i] < s[i + 1]:
break
i -= 1

if i >= 0:
for j in range(len(s) - 1, i, -1):
if s[j] > s[i]:
break
s[i], s[j] = s[j], s[i]

reverse(s, i + 1, len(s) - 1)
return ''.join(s)

def reverse(s: List[chr], l: int, r: int):
while l < r:
s[l], s[r] = s[r], s[l]
l += 1
r -= 1

s = nextPermutation(list(str(n)))
ans = int(s)
return -1 if ans > 2**31 - 1 or ans <= n else ans
``````