# Java Solution like Next Permutation Problem O(n)

• ``````public class Solution {
public int nextGreaterElement(int n) {
char[] a=(""+n).toCharArray();
int i = a.length - 2;
while (i >= 0 && a[i + 1] <= a[i]) {
i--;
}
if(i<0)
return -1;
int j = a.length - 1;
while (j >= 0 && a[j] <= a[i]) {
j--;
}
swap(a, i, j);
reverse(a, i + 1);
try{
return Integer.parseInt(new String(a));
}
catch(Exception e){
return -1;
}
}
private void reverse(char[] a, int start) {
int i = start, j = a.length - 1;
while (i < j) {
swap(a, i, j);
i++;
j--;
}
}
private void swap(char[] a, int i, int j) {
char temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}``````

• This post is deleted!

• This works , but I think we need to handle Integer MAX_VALUE cases as well, don't we?

``````       try{
return Integer.parseInt(res);
}catch(Exception e){
return -1;
}``````

• Your solution will fail for the 10 digit integers. Ex: 1999999999

• Same idea here, and a little modification:

``````public class Solution {
public int nextGreaterElement(int n) {
char[] arr=(n+"").toCharArray();
if(arr.length<=1)  return -1;
int i=arr.length-2;
//Find the rightmost element, which is not in a non-increasing sequence ending at arr[arr.length-1];
//For example, for 679833,  7 is the rightmost element, which is not in the non-increasing sequence 9,8,3,3.
while(i>=0&&arr[i]>=arr[i+1]){
i--;
}
if(i<0)   return -1;
int j = arr.length - 1;
//Find the smallest element larger than arr[i] in the non-increasing sequence.
//Here, 8 is the smallest element larger than 7 in the sequence 9,8,3,3.
while (arr[j] <= arr[i]) {
j--;
}
//Swap arr[i] with the element arr[j].
//Here, swap 7 with 8.
char tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
//Sort this newly modified non-increasing sequence, which is equivalent to reversing the sequence.
//Now, 9,7,3,3, becomes 3,3,7,9;
Arrays.sort(arr,i+1,arr.length);

//Use long to avoid overflow;
//Here, res=683379
long res=Long.parseLong(new String(arr));
return res>Integer.MAX_VALUE?-1:(int)res;
}
}
``````

• @vivek75 I have updated the solution. Thanks

• Why do you say it's O(n)? It's O(log n), isn't it?

Fascinating. Six people name a complexity class in their title, and all of them say O(n). (Well, one says O(N) and fails to say what they mean with N).

• Why do you say it's O(n)? It's O(log n), isn't it?

Fascinating. Six people name a complexity class in their title, and all of them say O(n). (Well, one says O(N) and fails to say what they mean with N).

Isn't this O(n) where n is number of digits in input or O(log n) where n is number?

• @suneelg Well, kind of. But n is the input number. That's defined in the problem.

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