```
public class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i + 1] <= nums[i]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1);
}
private void reverse(int[] nums, int start) {
int i = start;
int j = nums.length - 1;
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
```

We iterate through `nums`

from right to left to find the number `nums[i]`

where the descending order occurs for the first time. Then we scan through the nums from right to `i+1`

to find a number that is greater `nums[i]`

and swap the number with it. Finally, we reverse `nums[i+1] ... nums[nums.length-1]`

.

By doing so, we can guarantee that:

- The next permutation is always greater or equal to the current permutation (we assume the numbers in the current permutation are not sorted in descending order).
- There does not exist a permutation that is greater than the current permutation and smaller than the next permutation generated by the above code.
- If the numbers in the current permutation are already sorted in descending order (i.e. greatest possible value), the next permutation has the smallest value.

*Time Complexity*: `O(n)`

*Extra Space*: `O(1)`

## Discussion