Accepted Java Solution O(n) with explanations


  • 0
    M

    Algorithm:

    • 1.Traverse from right and identify the element such that num[i] < num[i+1] i.e. it breaks descending rule
    • a) If match not found we have reached the last element, so reverse the order of all elements
    • b) If match found, then traverse from right and identify the first element say num[i+x] that is greater than num[i]. Swap num[i] and num[i+x] and then reverse the order of elements to the right of num[i+x]

    Examples:
    (i) 3,2,1 -> 1,2,3 (1a)
    (ii) 1,3,2 -> 2,1,3 (1b)
    Steps:

    • 1 breaks descending rule
    • Swap(1,2) i.e. 2,3,1
    • Reverse all elements to the the right of 2 i.e. 2,1,3
    public static int[] nextPermutation(int[] nums) {
            if(nums.length == 0) {
                return null;
            }
    
            boolean isMatch = false;
            int i = nums.length-2;
            for( ; i>=0; ) {
                if(nums[i] < nums[i+1]) {
                    isMatch = true;
                    break;
                }
                i--;
            }
    
            if(isMatch) {
                //Found an element that breaks the descending rule (1b)
                //Find an element > nums[i+x] that is greater than num[i]
                int j=nums.length - 1;
                for(; j>i;) {
                    if(nums[j] > nums[i])
                        break;
                    j--;
                }
                swap(nums, i, j);
                //Note: Since i and j are swapped, reverse the elements to right of index i+1
                reverse(nums, i+1, nums.length-1);
            } else {
                //Not Found an element that breaks the descending rule (1a), i.e. we have reached the end of lexicographical order
                //Reverse all elements to get the first element in lexicographical order
                reverse(nums, 0, nums.length-1);
            }
    
            return nums;
        }
    
        public static void reverse(int[] nums, int s, int e){
            while(s < e){
                swap(nums, s, e);
                s++;
                e--;
            }
        }
    
        public static void swap(int[] nums, int s, int e){
            int t = nums[s];
            nums[s] = nums[e];
            nums[e] = t;
        }
    
        public static void main(String[] args) {
            //Tests
            nextPermutation(new int[] {1,3,2}); //2,1,3
            nextPermutation(new int[] {3,2,1}); //1,2,3
        }
    

    Note: I have a return type of int[] to allow running some unit tests. Hope this helps.
    Special thanks to hot13399 who provided the detailed algorithm here: https://leetcode.com/problems/next-permutation/discuss/13866


  • 0
    M
    This post is deleted!

Log in to reply
 

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