31. Next Permutation

/**

 * 31. Next Permutation

 * Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

 * If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

 * The replacement must be in place and use only constant extra memory.

 */

See solution to the problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/NextPermutation.java

This is unfair question to ask on interviews as it requires a fair amount of pre hand knowledge regarding lexicographic permutations to be able to solve this in a short amount of time.

But the question is interesting in that it explores flow of numbers in permutations, which is good to understand and hence I have included it here.

Some facts regarding lexicographic permutations:

1. A decreasing array is the last permutation of the array, and the next one is the reverse of it. For example, `3,2,1` is the last permutation of this array and `1,2,3` will be next.
2. For a decreasing subarray there is a number before the decreasing subarray which ‘leads’ to the decreasing subarray. I,e  for array ‘4,7,6,5,3,2,1’ 4 is the leading number before the decreasing subarray ‘7,6,5,3,2,1’. The logic to find the next permutation here is:
   1. Swap the leading 4 with the number that is greater than itself, in this case 5 so the array would become 5,7,6,4,3,2,1
   1. Reverse the decreasing subarray to right of the subarray I,e reverse the subarray to right of 4 above so that the array becomes 5,1,2,3,4,6,7

 You can look at this article on wiki pedia to understand more about permutations: https://en.wikipedia.org/wiki/Permutation       

Here is the code:

public void nextPermutation(int[] nums) {
    //step 1: find first index thats not in descending order from right
    int j = nums.length-1; boolean nonDesc = false;
    for (; j>0; j--) {
        if (nums[j-1] < nums[j]) {
            nonDesc = true;
            j--;
            break;
        }
    }
    if (!nonDesc) {
        Arrays.sort(nums);
        return;
    }
    //step 2: find first index from right thats higher than the index found above
    int i = nums.length-1;
    for (; i > j; i--) {
        if (nums[i] > nums[j]) {
            break;
        }
    }
    //step 3: swap i and j
    swap(nums, i, j);
    //step 4: the index right of this index are in descending order, change them to be in ascending order
    for (i =j+1, j = nums.length-1; j > i; j--,i++) {
        swap(nums, i, j);
    }
}