Easy Java solution with explanation


  • 0
    N
    • Find decreasing sequence ending at the last element of the array.
    • Invert this sequence.
    • The element on the immediate left of this sequence needs to be swapped with the next big number from the sequence.
    public class Solution {
        
        void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            return;
        }
        
        void invert(int[] nums, int left, int right) {
            while(left<right){
                swap(nums,left++,right--);
            }
        }
        
        public void nextPermutation(int[] nums) {
            // dsStart - first element in decreasing sequence that ends in last element
            int dsStart = nums.length-1; // ex: In {3,5,4,2,1} dsStart will be 1 ie. with val 5
            while (dsStart > 0 && nums[dsStart-1] >= nums[dsStart]) dsStart--;
            invert(nums,dsStart,nums.length-1);
            if (dsStart != 0) {
                int nextBigIdx = dsStart;
                while (nums[nextBigIdx] <= nums[dsStart-1])
                    nextBigIdx++;
                swap(nums,dsStart-1,nextBigIdx);
            }
            return;
        }
    }
    

Log in to reply
 

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