Java O(n) solution with explanation


  • 0
    M

    Idea:

    1. Find the index "sortIdx" after which the numbers are sorted in descending order.
    2. Find the index "swapIdx" which is the least number greater than nums[sortIdx-1] after sortIdx. (That is the last index greater than nums[sortIdx-1] since the subarray after sortIdx is sorted in descending order.)
    3. Swap sortIdx-1 and swapIdx-1.
    4. Reverse the subarray after sortIdx.
    public class Solution {
        
        public void nextPermutation(int[] nums) {
            if(nums==null || nums.length<=1) return;
            
            final int N = nums.length;
            int sortIdx = N-1; // numbers after sortIdx (include) is sorted in descending order 
            for(int i=N-1; i>=1 && nums[i]<=nums[i-1]; i--){
                sortIdx--;
            }
            if(sortIdx>0){
                int swapIdx = N;
                for(int i=N-1; i>=sortIdx && nums[i]<=nums[sortIdx-1]; i--){
                    swapIdx = i;
                }
                swap(nums, sortIdx-1, swapIdx-1);
            }
            reverse(nums, sortIdx, N-1);
        }
        
        private void swap(int[] nums, int i, int j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        
        private void reverse(int[] nums, int i, int j){
            while(i<j){
                swap(nums, i, j);
                i++; j--;
            }
        }
    }
    

Log in to reply
 

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