Next Permutation LeetCode Problem.

An interesting Algo Problem i found on LeetCode is the next permutation problem.

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

• For example, the next permutation of arr = [1,2,3] is [1,3,2].

• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].

• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

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

One solution would be to have generated all the permutation in an array of arrays, have them sorted, find the array we have, and take the next one as a solution. But this solution would be far from perfect, as it would use way to much time and memory.

Lets find out a better solution.

• take this example: [2, 4, 1, 7, 5, 0] should end up with [2, 4, 5, 0, 1, 7]

• First of all if the array is sorted in descending order, then we have only to inverse it

• Now lets have a pivot index. A pivot index is first element from the right that whose next right element is higher:
  e.g :[2, 4, 1, 7, 5, 0] → pivot index is 2 as its value 1, and it has an element higher than it on the right side: 7.

• on the right side from pivot, we find the right most element, higher than pivot: 5

• swap pivot with higher element so we get [2, 4, 5, 7, 1, 0]

• the right side of the pivot index (which is 2), should be reversed - [2, 4, 5, 0, 1, 7]

This is basically everything. Now lets go to the code solution.

public class NextPermutation_31 {    
    public static void main(String[] args) {
        int[] array = new int[]{2, 4, 1, 7, 5, 0};
        nextPermutation(array);
        System.out.println(Arrays.toString(array))
    }



    public static void nextPermutation(int[] nums) {
        if(nums.length < 2){
            return;
        }
        int pivotIndex = findPivotIndex(nums);
        if(pivotIndex == -1){
            reverse(nums);
        }else {
            int higherRightIndex = findHigherRightIndex(nums, pivotIndex +1, nums[pivotIndex]);
            swap(nums, pivotIndex, higherRightIndex);
            reverseStartWith(nums, pivotIndex + 1);
        }
    }


}

this is the alogo, however we need to implement those help methods: swap, findHigherRightIndex, reverse, reverseStartWith. The last 2 basically are the same: reverse is same with reverseStartWith starting at 0.

  static int findHigherIndexStartWith(int[] nums, int startWith, int valueToCompare) {
        for (int i = nums.length - 1; i >= startWith; i--) {
            if (nums[i] > valueToCompare) {
                return i;
            }
        }
        return 0;
    }

  static void reverse(int[] nums, int start) {
        for (int i = start; i < (nums.length + start) / 2; i++) {
            swap(nums, i, nums.length + start - 1 - i);
        }
    }

    static void swap(int[] nums, int i1, int i2) {
        int temp = nums[i1];
        nums[i1] = nums[i2];
        nums[i2] = temp;
    }

    static int findPivot(int[] nums) {
        int pivotIndex = -1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                pivotIndex = i;
                break;
            }
        }
        return pivotIndex;
    }

putting all together

public class NextPermutation {
    public static void main(String[] args) {
        int[] array = new int[]{2, 4, 1, 7, 5, 0};
        nextPermutation(array);
    }

    public static void nextPermutation(int[] nums) {
        int pivotIndex = findPivot(nums);
        if (nums.length < 2) {
            return;
        }
        if (pivotIndex == -1) {
            reverse(nums, 0);
        } else {
            swap(nums, pivotIndex, findHigherIndexStartWith(nums, pivotIndex + 1, nums[pivotIndex]));
            reverse(nums, pivotIndex + 1);
        }
    }

    static void reverse(int[] nums, int start) {
        for (int i = start; i < (nums.length + start) / 2; i++) {
            swap(nums, i, nums.length + start - 1 - i);
        }
    }

    static void swap(int[] nums, int i1, int i2) {
        int temp = nums[i1];
        nums[i1] = nums[i2];
        nums[i2] = temp;
    }

    static int findPivot(int[] nums) {
        int pivotIndex = -1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                pivotIndex = i;
                break;
            }
        }
        return pivotIndex;
    }

    static int findHigherIndexStartWith(int[] nums, int startWith, int valueToCompare) {
        for (int i = nums.length - 1; i >= startWith; i--) {
            if (nums[i] > valueToCompare) {
                return i;
            }
        }
        return 0;
    }
}