Next Permutation

Problem

Rearrange an array of numbers into the lexicographically next greater permutation, in place. If no such permutation exists, rearrange it as the lowest possible order.

Input:  nums = [1, 2, 3]
Output: [1, 3, 2]

Input:  nums = [3, 2, 1]
Output: [1, 2, 3]

Python Solution

def next_permutation(nums):
    n = len(nums)
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[i + 1:] = reversed(nums[i + 1:])
    return nums

C++ Solution

void nextPermutation(vector<int>& nums) {
    int n = nums.size();
    int i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        int j = n - 1;
        while (nums[j] <= nums[i]) j--;
        swap(nums[i], nums[j]);
    }
    reverse(nums.begin() + i + 1, nums.end());
}

Java Solution

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i >= 0) {
            int j = n - 1;
            while (nums[j] <= nums[i]) j--;
            int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp;
        }
        int left = i + 1, right = n - 1;
        while (left < right) {
            int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp;
            left++; right--;
        }
    }
}

Complexity

Time: O(n) — each of the three steps (find pivot, find swap target, reverse the suffix) scans a portion of the array at most once. Space: O(1) — the array is rearranged in place.