O(n) solution with a ton of explanation.

• 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;
}
}
``````

}
'''

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