Next Permutation - leetcode

nextPermutation.java

/*
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, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Algorithm:
Find the swap pair and swap them, then sort the right side in ascending order
1. swap pair is described below in the code.
2. need to take care of the edge case: when num is the max.
*/
public class Solution {
    public void nextPermutation(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        // check if it reach the max of the num
        if(isMax(num)) {
            // edge case: when num is the max
            reverse(num, 0, num.length - 1);
            return;
        }
        
        // Find the first small number from right to left
        // swap it with the lowest number that greater than that
        // on its right.
        // And minimize its right side
        int i = num.length - 1;
        int j = i;
        for(; i >= 1; i--) {
            if(num[i] > num[i-1]) break; // i-1 is the one need to be swap.
        }
        for(; j >= 0; j--) {
            if(num[j] > num[i-1]) break; // find the right most one that is greater than that.
        }
        swap(num, i-1, j);
        // minimize the right side from right most to i
        reverse(num, i, num.length-1);
        insertion_sort(num, i, num.length-1);
        return;
    }
    
    public boolean isMax(int[] num) {
        for(int i = 0; i < num.length-1; i++) {
            if(num[i] < num[i+1]) return false;
        }
        return true;
    }
    
    public void reverse(int[] num, int start, int end) {
        int left = start;
        int right = end;
        while(right > left) {
            swap(num, left, right);
            left++;
            right--;
        }
        return;
    }
    
    public void swap(int[] num, int idx1, int idx2) {
        int tmp = num[idx1];
        num[idx1] = num[idx2];
        num[idx2] = tmp;
        return;
    }
    
    public void insertion_sort(int[] num, int start, int end) {
        // insertion sort since this num is almost sorted array
        for(int i = start; i < end-1; i++) {
            if(num[i] > num[i+1]) {
                int tmp = num[i+1];
                for(int j = i; j >= start; j--) {
                    if(num[j] > tmp) {
                        num[j+1] = num[j];
                    } else {
                        num[j] = tmp;
                        break;
                    }
                }
            }
        }
        return;
    }
}