# Java(5ms) - Find - Swap - Sort Solution

• From right to left, the idea is to find the number greater than `num[i]`, swap it, and sort the rest of the elements to the right.

``````public int nextGreaterElement(int n) {
char[] num = (n + "").toCharArray();
for(int i = num.length-2; i >= 0; i--) {
// find min number greater than num(i)
int minIdx = i;
for(int j = i+1; j < num.length; j++) {
minIdx = num[j] > num[i] ? j : minIdx;
}
if(minIdx != i) {
char temp = num[i]; //swap minIdx and i;
num[i] = num[minIdx];
num[minIdx] = temp;

Arrays.sort(num, i+1, num.length);

long val = Long.parseLong(new String(num));
return (val <= Integer.MAX_VALUE) ? (int) val : -1;
}
}
return -1;
}``````

• @jaqenhgar how is it find minIdx ?

• My idea is the same in general. I have decided to share my code below.

``````public class Solution {

private List<Integer> parseDigits(int n){
List<Integer> res = new ArrayList<>();
while(n != 0){
n/=10;
}
return res;
}

private int makeNumber(int [] digs){
int res= 0;
int p = 1;
for(int dig:digs){
res+=dig*p;
p*=10;
}
return res;
}

private void swap(int nums[], int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}

private void reverse(int nums[], int i, int j){
int l = i;
int r = j-1;
while(l<r){
swap(nums, l, r);
l++;
r--;
}

}

public int nextGreaterElement(int n) {
if(n == 0) return n;
List<Integer> digs =  parseDigits(n);
int [] nums = new int[digs.size()];
for(int i = 0;i<digs.size();i++) nums[i] = digs.get(i);
for(int i = 0;i<nums.length;i++){
int cur = nums[i];
Arrays.sort(nums,0,i);
for(int j = 0;j<i;j++){
if(nums[j] > cur){
swap(nums, i, j);
break;
}
}
Arrays.sort(nums, 0, i);
reverse(nums, 0, i);
int m = makeNumber(nums);
if(m >n) return m;
}
return -1;
}
}``````

• This post is deleted!

• It's already sorted, so it takes 2ms more.

``Arrays,sort(num, i+1 num.length);``

• @jaqenhgar My idea is also like this,but your program is so Short and simple.

• @hantong It is, but it's in the reverse order. I'm using sort to reverse it.

• i've got almost the same idea but w/o sorting, which takes 3ms:

``````public class Solution {
public int nextGreaterElement(int n) {
int m = n, size = 0, peak = 1, list[] = new int[10];
while (m != 0) {
list[size++] = m % 10;
m /= 10;
}

while (peak < size) {
if (list[peak] < list[peak - 1]) {
int cursor = 0, result = 0;
while (list[cursor] <= list[peak]) cursor++;
int tmp = list[cursor];
list[cursor] = list[peak];
list[peak] = tmp;
for (int i = size - 1; i >= peak; i--) result = result * 10 + list[i];
for (int j = 0; j < peak; j++) result = result * 10 + list[j];
return result > n ? result : -1;
}
peak++;
}
return -1;
}
}
``````

• I'm not even able to read the question. WTF, could someone explain this problem in a simple way to me?

• @danielz92 Consider the number `3142`. You need to get the first number which is greater than `3142`, but the condition is that you've the reuse the numbers in 3142, that is - `[3,1,4,2]`

If you look at it, some of the possible numbers are, 3412, 4213, 3241, 3214, etc.. (all greater than 3142). But the least among them is `3214`, which is what this question asks you to find.

• @jedxin It doesn't.

Made a slight change on finding the minIdx (AKA, the index of the smallest number that is larger than the current digit):

``````           //set minIdx to be current digit
int minIdx = i;
//find the first digit that is greater than current digit
for (int k = i; k < num.length; ++k) {
if (num[k] > num[minIdx]){
minIdx = k;
break;
}
}
//continue to search if this index is "minimal", if not, update
for(int j = i+1; j < num.length; j++) {
if (num[j] > num[i] && minIdx != i && num[j] < num[minIdx])
minIdx = j;
}
``````

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