O(N) Clean Java solution


  • 0
    A
    public void nextPermutation(int[] nums) {
    	int j = nums.length - 1;
    	while (j > 0 && nums[j - 1] >= nums[j]) j--; // find the longest increasing sequence from right
    
    	if (j == 0) { Arrays.sort(nums); return; } // if already largest permutation, just sort it
    
    	int pivot = j - 1; // mark pivot
    	j = nums.length - 1;
    	while (j > pivot && nums[pivot] >= nums[j]) j--; // find the first right most value larger than pivot
    
    	swap(nums, pivot, j); 
    	reverse(nums, pivot + 1, nums.length - 1);
    }
    
    void reverse(int[] nums, int i, int j) {
    	while (i < j)
    		swap(nums, i++, j--);
    }
    
    void swap(int[] nums, int i, int j) {
    	int t = nums[j];
    	nums[j] = nums[i];
    	nums[i] = t;
    }

Log in to reply
 

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