## DEV Community

Kaitian Xie

Posted on • Updated on

# LeetCode 31. Next Permutation

``````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:

1. 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).
2. There does not exist a permutation that is greater than the current permutation and smaller than the next permutation generated by the above code.
3. 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)`