# Simple O(n) Java solution

• This is a simple solution that is O(n) if you disregard sort operations.

``````public int nextGreaterElement(int n) {
char[] chars = String.valueOf(n).toCharArray();
int l = chars.length - 1;
int x = -1;
int j;

// Find first position where x = left digit < right digit.
for (int i = l; i >= 1; i--) {
if (chars[i - 1] < chars[i]) {
x = i - 1;
break;
}
}

// If can't find, n is maximal.
if (x == -1) return -1;

// At this point, as the digits after x are sorted and the loop above implies
//      chars[x] < chars[x - 1]
// We try to find a digit to swap x with by searching for an index j such that
//      chars[j] < chars[x]
// If found, swap and then sort to get the next greater element.
for (j = x + 1; j <= l; j++) {
if (chars[j] <= chars[x]) {
swap(chars, j - 1, x);
Arrays.sort(chars, x + 1, l + 1);
Long longVal = Long.valueOf(new String(chars));
return longVal <= Integer.MAX_VALUE ? longVal.intValue() : -1;
}
}

// If we hit the end without finding the position it's because the digits
// at the right of x in the string are all equal and/or are all greater than chars[x].
// In both cases the last position l represents the smallest number greater than n
// so swap with last position and then sort.
swap(chars, x, l);
Arrays.sort(chars, x + 1, l + 1);
Long longVal = Long.valueOf(new String(chars));
return longVal <= Integer.MAX_VALUE ? longVal.intValue() : -1;
}

private void swap(char[] arr, int a, int b) {
char t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}

``````

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