LeetCode 31. Next Permutation

Question

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are considered permutations of arr: [1,2,3], [1,3,2], [3,1,2], [2,3,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

• For example, the next permutation of arr = [1,2,3] is [1,3,2].
• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

Source: https://leetcode.com/problems/next-permutation/

Solution

Our idea is similar to carry in addition. We need to find the longest non-increasing suffix and perform a carry operation on this suffix, so that we get the next permutation.

Specifically, we swap the digit before this suffix (nums[pivot]) with an element just greater than the digit (from right to left in the suffix, find the first element that is larger than the pivot). Then we reverse the suffix to make it non-decreasing so that the new suffix is the “smallest” permutation of itself. Here are several points worth noting. First, an element greater than pivot must exist in the suffix. Because this suffix is the longest non-increasing suffix, pivot at least is smaller than the first element in the suffix. Second, after swap, the new suffix is still non-increasing because elements in the left of the swap position must be equal to or less than the pivot. This is guaranteed by our search strategy.

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

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

// Time Complexity, O(n)
public void nextPermutation(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return;
    }
    // find the longest non-increasing suffix
    int pivot = nums.length - 2;
    // find the pivot before the longest non-increasing suffix
    while (pivot >= 0 && nums[pivot] >= nums[pivot + 1]) {
        pivot--;
    }
    if (pivot >= 0) {
        // from right to left in the suffix, find the first element that is larger than the pivot
        // "first" is important for keeping suffix non-increasing
        int j = nums.length - 1;
        for (; j >= pivot + 1; j--) {
            if (nums[j] > nums[pivot]) {
                break;
            }
        }
        // swap and make the suffix non-decreasing by reversing it
        swap(nums, pivot, j);
        reverse(nums, pivot + 1, nums.length - 1);
    } else { // nums is the last permutation
        // turn it to the first permutation
        reverse(nums, pivot + 1, nums.length - 1);
    }
}

Example