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. 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. 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 backw