☕ DSA Java Articles

Topics › Arrays › Medium

Next Permutation

Medium TUF ID 31 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A permutation of an array is any reordering of its elements. If we list all permutations of the array in lexicographic (dictionary) order, the next permutation of nums is the one that comes immediately after it in that list. Rearrange nums into its next permutation, in place, using only constant extra memory. If nums is already the last permutation (sorted in non-increasing order), wrap around to the first one (sorted in non-decreasing order).

Constraints: 1 ≤ n ≤ 100, 0 ≤ nums[i] ≤ 100 on LeetCode; the method works for any int values and duplicates are allowed.

Example 1

nums = [1, 2, 3]
answer = [1, 3, 2]       // the permutations in order are 123, 132, 213, 231, 312, 321

Example 2

nums = [3, 2, 1]
answer = [1, 2, 3]       // 321 is the last permutation, so wrap to the first

Example 3

nums = [1, 1, 5]
answer = [1, 5, 1]       // duplicates are fine

Approach 1: Brute force, generate every permutation

Intuition. The definition talks about “the list of all permutations in order”, so the most literal solution is to build that list. Generate every distinct permutation, sort them lexicographically, find the input in the sorted list, and copy the one after it (wrapping to the first). Duplicates need care: [1, 1, 5] has only three distinct permutations, not six, and we must not list [1, 1, 5] twice or the “next” one would be itself. The generator below avoids that by never placing the same value at the same position twice.

Algorithm.

  1. Recursively generate all distinct permutations: for position idx, try each distinct value found at idx..n-1, swap it in, recurse, swap it back.
  2. Sort the generated permutations lexicographically.
  3. Locate the input, take the following permutation (index (i + 1) mod size) and copy it into nums.
static void bruteForce(int[] nums) {
    List<int[]> all = new ArrayList<>();
    generate(nums.clone(), 0, all);
    all.sort(P31_NextPermutation::compareLex);
    for (int i = 0; i < all.size(); i++) {
        if (Arrays.equals(all.get(i), nums)) {
            int[] next = all.get((i + 1) % all.size());   // wrap around after the last permutation
            System.arraycopy(next, 0, nums, 0, nums.length);
            return;
        }
    }
}

private static void generate(int[] a, int idx, List<int[]> out) {
    if (idx == a.length) {
        out.add(a.clone());
        return;
    }
    Set<Integer> used = new HashSet<>();            // a value placed at idx once must not be placed again
    for (int i = idx; i < a.length; i++) {
        if (!used.add(a[i])) continue;
        swap(a, idx, i);
        generate(a, idx + 1, out);
        swap(a, idx, i);
    }
}

private static int compareLex(int[] x, int[] y) {
    for (int i = 0; i < x.length; i++) {
        if (x[i] != y[i]) return Integer.compare(x[i], y[i]);
    }
    return 0;
}

Complexity. Time O(n! × n): there are up to n! permutations, each costs O(n) to copy and O(n) per comparison during the sort (O(n! log n!) comparisons). Space O(n! × n) to hold them all. For n = 10 that is 3.6 million arrays; for n = 15 it is hopeless. We need to find the next permutation without looking at the others.

Approach 2: Optimal, pivot, successor, reverse

Intuition. Think about how you would find the next word in a dictionary. You keep as long a prefix as possible unchanged and make the smallest possible change at the end. Look at the array from the right: as long as the suffix is non-increasing (nums[i] >= nums[i+1]), that suffix is already the largest arrangement of its own elements, so no rearrangement of it alone can produce a bigger permutation. The first position from the right where the sequence increases, nums[i] < nums[i+1], is the pivot: that is the rightmost position whose value can be bumped up.

To bump it up by the smallest possible amount, swap nums[i] with the smallest element to its right that is still larger than it. Because the suffix is non-increasing, scanning from the right and stopping at the first nums[j] > nums[i] finds exactly that element. After the swap the suffix is still non-increasing (we replaced a value with one just above it and put a value just below in its place), so it is still the largest arrangement of its elements. We want the smallest, so reverse it.

If no pivot exists, the whole array is non-increasing, meaning it is the last permutation; reversing the whole thing yields the first one, which is the required wrap-around.

Algorithm.

  1. Find the largest i such that nums[i] < nums[i + 1]. If none exists, reverse the whole array and stop.
  2. Find the largest j > i such that nums[j] > nums[i], and swap nums[i] with nums[j].
  3. Reverse the suffix nums[i + 1 .. n - 1].
static void optimal(int[] nums) {
    int n = nums.length;
    int pivot = -1;
    for (int i = n - 2; i >= 0; i--) {          // 1. rightmost i with nums[i] < nums[i + 1]
        if (nums[i] < nums[i + 1]) {
            pivot = i;
            break;
        }
    }
    if (pivot == -1) {                          // whole array is non-increasing: it is the last permutation
        reverse(nums, 0, n - 1);
        return;
    }
    for (int j = n - 1; j > pivot; j--) {       // 2. rightmost j with nums[j] > nums[pivot]: the smallest value larger than the pivot
        if (nums[j] > nums[pivot]) {
            swap(nums, pivot, j);
            break;
        }
    }
    reverse(nums, pivot + 1, n - 1);            // 3. suffix is still non-increasing; reversing makes it the smallest arrangement
}

private static void swap(int[] a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

private static void reverse(int[] a, int lo, int hi) {
    while (lo < hi) swap(a, lo++, hi--);
}

Dry run on nums = [1, 5, 8, 4, 7, 6, 5, 3, 1]:

Step Observation Array
find pivot suffix 7, 6, 5, 3, 1 is non-increasing; 4 < 7 at index 3 pivot = 3
find successor from the right, first value > 4 is 5 at index 6 swap indices 3 and 6
after swap   [1, 5, 8, 5, 7, 6, 4, 3, 1]
reverse suffix indices 4..8 [1, 5, 8, 5, 1, 3, 4, 6, 7]

Why > and not >= when looking for the pivot? With duplicates, [1, 5, 1] has pivot at index 0 (1 < 5), and the suffix 5, 1 is non-increasing. If we used <= to detect the pivot we would stop at equal neighbours and swap two equal values, producing the same permutation again. Strict comparison keeps the result correct with repeated values, and [1, 1, 5] -> [1, 5, 1] in the tests exercises exactly this.

Complexity. Time O(n): each of the three steps is a single pass over at most n elements. Space O(1): the array is modified in place with a few index variables.

Edge cases and pitfalls