# Java O(n) solution with explanation

• Idea:

1. Find the index "sortIdx" after which the numbers are sorted in descending order.
2. Find the index "swapIdx" which is the least number greater than nums[sortIdx-1] after sortIdx. (That is the last index greater than nums[sortIdx-1] since the subarray after sortIdx is sorted in descending order.)
3. Swap sortIdx-1 and swapIdx-1.
4. Reverse the subarray after sortIdx.
``````public class Solution {

public void nextPermutation(int[] nums) {
if(nums==null || nums.length<=1) return;

final int N = nums.length;
int sortIdx = N-1; // numbers after sortIdx (include) is sorted in descending order
for(int i=N-1; i>=1 && nums[i]<=nums[i-1]; i--){
sortIdx--;
}
if(sortIdx>0){
int swapIdx = N;
for(int i=N-1; i>=sortIdx && nums[i]<=nums[sortIdx-1]; i--){
swapIdx = i;
}
swap(nums, sortIdx-1, swapIdx-1);
}
reverse(nums, sortIdx, N-1);
}

private void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}

private void reverse(int[] nums, int i, int j){
while(i<j){
swap(nums, i, j);
i++; j--;
}
}
}
``````

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