Next Permutation

Medium Problem 15 of 151 Java and Python

Problem

The next permutation of an array is the next arrangement of its numbers in dictionary (lexicographic) order. For [1, 2, 3] it is [1, 3, 2].

Given nums, rearrange it in place into its next permutation. If it is already the largest arrangement (sorted in descending order), rearrange it into the smallest one (ascending order).

Example 1

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

Example 2

Input: nums = [3, 2, 1]
Output: [1, 2, 3]
Why: Already the last permutation, so wrap around to the first.

Example 3

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

Constraints

1 ≤ nums.length ≤ 100
0 ≤ nums[i] ≤ 100
Use only O(1) extra memory.

Explanation

To get the very next arrangement, change the array as far to the right as possible. Scan from the right for the first position i where nums[i] < nums[i + 1]: everything after it is in descending order, so that suffix is already at its largest.

Swap nums[i] with the smallest number in the suffix that is larger than it, then reverse the suffix so it becomes as small as possible.

Approach 1 · Naive

List every permutation

Time O(n! · n)
Space O(n! · n)

Generate every distinct permutation in sorted order, find the current one and copy the one after it (wrapping to the first). Only usable for tiny inputs: there are up to n! permutations.

Generate all distinct permutations of the numbers in lexicographic order.
Find the index of the current arrangement.
Copy the next permutation (or the first if it is the last) into nums.

Java

import java.util.*;

class Solution {
    public void nextPermutation(int[] nums) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        List<List<Integer>> all = new ArrayList<>();
        build(sorted, new boolean[sorted.length], new ArrayList<>(), all);
        List<Integer> current = new ArrayList<>();
        for (int num : nums) {
            current.add(num);
        }
        int index = all.indexOf(current);
        List<Integer> next = all.get((index + 1) % all.size());
        for (int i = 0; i < nums.length; i++) {
            nums[i] = next.get(i);
        }
    }

    // Builds permutations in sorted order, skipping repeated values.
    private void build(int[] sorted, boolean[] used, List<Integer> path, List<List<Integer>> all) {
        if (path.size() == sorted.length) {
            all.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < sorted.length; i++) {
            if (used[i] || (i > 0 && sorted[i] == sorted[i - 1] && !used[i - 1])) {
                continue;
            }
            used[i] = true;
            path.add(sorted[i]);
            build(sorted, used, path, all);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

Python

from itertools import permutations

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        everything = sorted(set(permutations(nums)))
        index = everything.index(tuple(nums))
        nums[:] = everything[(index + 1) % len(everything)]

Approach 2 · Optimal

Pivot, swap, reverse

Time O(n)
Space O(1)

Find the rightmost position that can be increased, bump it up by the smallest possible amount, and make everything after it as small as possible.

From the right, find the first i with nums[i] < nums[i + 1] (the pivot).
If there is a pivot, find from the right the first j with nums[j] > nums[i], and swap them.
Reverse the part after i (the whole array if there was no pivot).

Java

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

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            swap(nums, left++, right--);
        }
    }

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

Python

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i >= 0:
            j = len(nums) - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1:] = reversed(nums[i + 1:])

Complexity compared

Approach	Time	Space
Naive List every permutation	O(n! · n)	O(n! · n)
Optimal Pivot, swap, reverse	O(n)	O(1)

Key takeaways

The suffix after the pivot is always descending, so reversing it sorts it ascending in O(n).
Use >= and <= in the scans so duplicates such as [1, 5, 1] work.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem