O(n) solution with a ton of explanation.


  • 0

    Inspired by @yuyibestman
    '''
    /*
    Question is to find the number formed by the array to be "just" higher than the input given basically next possible increaed number. Steps:
    1. Find the first sequence from behind such that nums[i-1]<nums[i]
    2. Now we basically have to swap this (i-1)th number with any number between (i-1) and end of array such that the number chose is just higher than (i-1)th number
    3. Once that is done last step is to actually reverse all the numbers after (i-1) to end of the array so that the final formed number is "just" (next) higer than the original
    For example:
    121543321 so the 1 at index 2 is smaller than 5 now we have to swap 1 with number between index 2 and n-1 such that it is just higer so we can swap it with 2 at index 7. Last step is to reverse all after index 2.
    so 121543321 -> 122543311 -> 122113345
    */
    public class Solution {
    public void nextPermutation(int[] nums) {
    if(nums.length<2)
    return;
    int i = nums.length-1;
    while(i>0){
    if(nums[i-1]<nums[i]){
    break;
    }
    i--;
    }
    //At this point i is point to the number whose i-1 is less than i. in example 5
    if(i==0){ //that means such arrangment is not possible so as per question basically sort is ascending
    reverse(nums, 0, nums.length-1);
    return;
    }

        //Else do the step 2.
        int val = nums[i-1];
        int j=nums.length-1;
        while(j>=i){ //Go from end to i;
            if(nums[j]>val){ //First number greater than i-1th val basically will be the smallest
                swap(nums, j, i-1);
                break;
            }
            j--;
        }
        
        //Do the step 3
        reverse(nums, i, nums.length-1);
        return;
    }
    
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    public void reverse(int[] nums, int i, int j){
        while(i<=j){
            int temp=nums[i];
            nums[i++]=nums[j];
            nums[j--]=temp;
        }
    }
    

    }
    '''


Log in to reply
 

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