# Simple O(n) 0ms solution (this is essentially next permutation)

• Like the problem of finding next permutation, the key to this problem is to find the first digit[i] which is smaller than digit[i+1] going from right to left. And then we need to find the first smallest digit[j] going from right to left and greater than digit[i].

Then we just need to swap digit[i] and digit[j], then sort the sub range from [i+1, n) in ascending order.

If we cannot find such pair of digit[i] and digit[j] we return -1.
If the newly generated num is greater than INT_MAX we also return -1.

``````class Solution {
public:
int nextGreaterElement(int n) {
if (n <= 0) return -1;

string num = to_string(n);
if (num.size() < 2) return -1;

int lhs = num.size() - 2;
while (lhs >= 0) {
if (num[lhs] < num[lhs+1]) break;
lhs--;
}
if (lhs == -1) return -1;

int rhs = num.size() - 1;
while (rhs > lhs) {
if (num[rhs] > num[lhs]) break;
rhs--;
}
if (lhs == rhs) return -1;

swap(num[lhs], num[rhs]);
sort(num.begin()+lhs+1, num.end());

istringstream istr(num);
long long value;
istr >> value;
return value > INT_MAX ? -1 : value;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.