Leetcode 31: Next Permutation

Question :
 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

Example:
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Idea :

Scan from right to left and find the first element that is less that its previous.
eg: 1 6 3 5 -> here it is 3. Let's name it as index.

1. Again scan from right to left and find the first element that is greater than 3 and that's 5. Let's mark it as idx. 3.In this step we swap 3 and 5.
2. Reverse elements from index+1 till the array length.

Code:

public void nextPermutation(int[] nums) {
int index = -1;
for(int i=nums.length-1;i>0;i--){
if(nums[i]>nums[i-1]){
index = i-1;
break;
}
}
if(index==-1){
reverse(nums,0,nums.length-1);
return;
}
int idx=0;
for(int i=nums.length-1;i>=index+1;i--){
if(nums[i]>nums[index]){
idx=i;
break;
}
}
swap(nums,index,idx);
reverse(nums,index+1,nums.length-1);
}
void swap(int[] nums,int i,int j){
int temp =nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
void reverse(int[] nums,int i ,int j){
while(i<j){
swap(nums,i,j);
i++;
j--;
}
}

Code Explanation :
We first initialize index=-1 and traverse backward to find the first one with i that satisfy the condition nums[i]>nums[i-1] . We assign this to index and break out of the loop.

for(int i=nums.length-1;i>0;i--){
if(nums[i]>nums[i-1]){
index = i-1;
break;
}
}


Next step we are discussing a corner case. For example if the given array is 3,2,1 then we cannot find the element that satisfies the previous condition. So when the array is given in decreasing order we just reverse it and return.

if(index==-1){
reverse(nums,0,nums.length-1);
return;
}

Next iteration we are considering another variable idx and traverse backward to find the 1st element that is greater than nums[index]. And assign it to idx and break out of the loop.

`for(int i=nums.length-1;i>=index+1;i--){
if(nums[i]>nums[index]){
idx=i;
break;
}
}

`
Here we swap the elements in position index and idx.

swap(nums,index,idx);
The last step is to make the remaining higher position part as small as possible, we just have to reverse the array from index+1 to nums.length-1.

reverse(nums,index+1,nums.length-1);

---

Time Complexity : O(n)
Aux Space : O(1)
I hope this helps you to understand the question and solution better.
Happy Coding :)