Java AC Solution


  • 2
    C

    Inspired by @TWiStErRob, basically the idea is find the index of last peak element, then find the element which is greater than the last peak element and then swap them. Once you swap those values, reverse the list after that element. See picture here for better understanding : https://www.nayuki.io/res/next-lexicographical-permutation-algorithm/next-permutation-algorithm-thumb.png

    public void nextPermutation(int[] nums) {
        int pivot = indexOfLastPeak(nums) - 1;
        if(pivot != -1){
            int pivotSuccessor = lastIndexOfGreater(nums, nums[pivot]);
            int temp = nums[pivot];
            nums[pivot] = nums[pivotSuccessor];
            nums[pivotSuccessor] = temp;
        }
        int start = pivot + 1, end = nums.length - 1;
        while(start < end){
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }
    
    
    private int indexOfLastPeak(int [] nums){
        for(int i = nums.length - 1 ; i > 0; i--){
            if(nums[i] > nums[i - 1]) return i;
        }
        return 0; /** first index */
    }
    
    private int lastIndexOfGreater(int [] nums, int threshold){
        for(int i = nums.length - 1 ; i >= 0; i--){
            if(nums[i] > threshold) return i;
        }
        return -1; /** shouldn't be executed */
    }
    

  • 0
    H

    Nice graph explanation!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.