Accepted Recursive Java Solution


  • 0
    V

    The idea is to reduce the problem into a swap operation of two rightmost elements (base case). If that is not possible we expand by adding the next immediate element and try to swap it with the smallest available number. When that swap is successful we need to sort the rest of the unswapped elements to the right to account for lexicography. If that swap is not successful that means we don't have a solution and return the array in ascending order.

    public static void nextPermutation(int[] nums)
    {
        if(nums.length == 1)
            return;
        boolean solved = solveSmaller(nums, 0, nums.length - 1);
        if(!solved){
            Arrays.sort(nums);
        }
    }
    
    static boolean solveSmaller(int nums[], int begin, int end){
        if(end - begin + 1 == 2){ //base case, compare two elements and swap if possible
            if(nums[begin] < nums[end]){
                swap(nums, begin, end);
                return true;
            }else{
                return false; //no swap available
            }
        }else{
            boolean isSmallerSolvable = solveSmaller(nums, begin + 1, end);
            if(isSmallerSolvable){
                return true;
            }else{ //compare the initial number with the rest and pick the smallest bigger number than the initial, and swap them
                int smallestBiggerIndex = pickSmallestBigger(nums[begin], nums, begin + 1); //O(n) operation
                if(smallestBiggerIndex == -1) {
                    return false;
                }else{
                    swap(nums, begin, smallestBiggerIndex);
                    Arrays.sort(nums, begin + 1, nums.length); //now that most significant index is at its place, the rest of the array should be in ascending order to satisfy lexicography
                    return true;
                }
            }
        }
    }
    
    static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    static int pickSmallestBigger(int num, int nums[], int begin){
        int pickedIndex = -1;
        int smallestBigger = Integer.MAX_VALUE;
        for(int i = begin; i < nums.length; i++)
        {
            if(nums[i] > num){
                if(nums[i] < smallestBigger){
                    smallestBigger = nums[i];
                    pickedIndex = i;
                }
            }
        }
        return pickedIndex;
    }

Log in to reply
 

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