# [JAVA] 3 rules for next number / T : O(N), S : O(N)

• ``````class Solution {

//12345 -> 12354 -> 12435 -> 12453 -> 12534 -> 12543 -> 13245 -> 13254 ->13425 -> 13452 -> 13524

public int nextGreaterElement(int n) {
char[] chs = String.valueOf(n).toCharArray();
int pivot = -1;
for(int i = chs.length-1; i > 0; i--) { // O(N)
if(chs[i] > chs[i-1]){
pivot = i;
break;
}
}

// Descending order,
if(pivot == -1){
return -1;
}

// Find smallest great number for chs[pivot - 1], O(N)
int smallest = pivot;
int smallest_last = pivot;
for(int i = pivot; i < chs.length; i++){
if(chs[i] > chs[pivot-1]){
if(chs[smallest] > chs[i]){
smallest = i;
smallest_last = i;
}
else if(chs[smallest] == chs[i])
smallest_last = i;
}
}

char temp = chs[pivot-1];
chs[pivot-1] = chs[smallest];
chs[smallest] = temp;

// Reverse below numbers
reverse(chs, smallest, smallest_last); // Consider 333 => 233 => 332
reverse(chs, pivot, chs.length-1);

// If number is bigger than Integer.MAX_VALUE
String result = String.valueOf(chs);
if(Long.parseLong(result) > Integer.MAX_VALUE)
return -1;

return Integer.parseInt(result);
}

public void reverse(char[] chs, int i, int j){
while(i < j){
char temp = chs[i];
chs[i] = chs[j];
chs[j] = temp;
i++; j--;
}
}
}
``````

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