31. Leetcode: 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.

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

public class NextPermutation {

    /*
    Algorithm:
    1. Find the first decreasing number from the right - saveIndex
    2. Find the first number that is just greater than the number at saveIndex - nextHighIndex
    3. Swap numbers at saveIndex and nextHighIndex
    4. Reverse everything to the right of saveIndex

    Complexity:
    Time complexity : O(n). In worst case, only two scans of the whole array are needed.
    Space complexity : O(1). No extra space is used. In place replacements are done.
     */
    public static void nextPermutation(int[] nums) {
        int l = nums.length;
        int i = l - 2;
        int j = l - 1;

        while(i >= 0 && nums[i] >= nums[i+1]) {
            i--;        // when the loop breaks i will be the saveIndex
        }
        System.out.println(i);
        if(i >= 0) {    // if i < 0, it means the array is strictly descending order
            while(j >= 0 && nums[j] < nums[i]) {
                j--;        // when the loop breaks j will be the nextHighIndex
            }
            System.out.println(j);
            swap(nums, i , j);
        }
        reverse(nums, i+1);
    }

    private static void reverse(int[] nums, int start) {
        int end = nums.length - 1;
        while(start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }

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

    public static void main(String[] args) {
        int nums[] = {1, 5, 8, 4, 7, 6, 5, 3, 2};
        nextPermutation(nums);
        System.out.println("Next permutation list: " + Arrays.toString(nums));
    }
}

Leetcode Problem Link:

https://leetcode.com/problems/next-permutation/