Next Permutation

Medium Arrays & Hashing Right to Left Traversal Original on LeetCode

Next Permutation is a medium arrays & hashing problem solved with the right to left traversal pattern. The best approach, optimal (find the pivot, swap, reverse the tail), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every arrangement) up.

Problem

An arrangement of an array’s values can be ranked in dictionary order: compare two arrangements at the first index where they differ, and the one with the smaller value there comes first.

Given an integer array nums, rearrange it in place into the arrangement that comes right after it in that order. If nums is already the largest possible arrangement, rearrange it into the smallest one (ascending order) instead. Use only constant extra memory.

Examples

Example 1

Input
nums = [2, 4, 3, 1]
Output
[3, 1, 2, 4]
Why
The arrangements of these four values that come after [2, 4, 3, 1] in dictionary order start with [3, 1, 2, 4].

Example 2

Input
nums = [5, 4, 2]
Output
[2, 4, 5]
Why
[5, 4, 2] is already the largest arrangement, so it wraps around to the smallest one.

Example 3

Input
nums = [1, 3, 3]
Output
[3, 1, 3]
Why
Equal values count once: the arrangements in order are [1, 3, 3], [3, 1, 3], [3, 3, 1].

Constraints

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100
  • Modify nums in place using only O(1) extra memory.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every arrangement)O(n! · n)O(n)
Optimal (find the pivot, swap, reverse the tail)O(n)O(1)

1Brute force (try every arrangement)

TimeO(n! · n)There are n! arrangements and each comparison or copy costs O(n).
SpaceO(n)The recursion depth and the two tracked arrays are O(n).

Generate every arrangement of the values. Among those that are strictly larger than the current array in dictionary order, take the smallest. If none is larger, take the smallest arrangement overall.

  1. Generate every permutation by swapping elements into each position recursively.
  2. Track the smallest permutation that is greater than nums, and the smallest permutation overall.
  3. Copy the first one into nums if it exists, otherwise the second.
class Solution {
    private int[] best, smallest, orig;

    public void nextPermutation(int[] nums) {
        orig = nums.clone();
        best = null;
        smallest = null;
        build(nums.clone(), 0);
        int[] res = best != null ? best : smallest;
        System.arraycopy(res, 0, nums, 0, nums.length);
    }

    private void build(int[] a, int k) {
        if (k == a.length) {
            if (smallest == null || cmp(a, smallest) < 0) smallest = a.clone();
            if (cmp(a, orig) > 0 && (best == null || cmp(a, best) < 0)) best = a.clone();
            return;
        }
        for (int i = k; i < a.length; i++) {
            int t = a[k]; a[k] = a[i]; a[i] = t;
            build(a, k + 1);
            t = a[k]; a[k] = a[i]; a[i] = t;
        }
    }

    private int cmp(int[] x, int[] y) {
        for (int i = 0; i < x.length; i++) {
            if (x[i] != y[i]) return x[i] < y[i] ? -1 : 1;
        }
        return 0;
    }
}

2Optimal (find the pivot, swap, reverse the tail)

TimeO(n)At most three linear passes: find the pivot, find the swap partner, reverse the tail.
SpaceO(1)Everything happens in place with a few indices.

Scan from the right for the first position i where nums[i] < nums[i + 1]. Everything after i is a descending tail, which is already its largest arrangement, so nums[i] is the position that must grow. Swap it with the smallest value in the tail that is larger than it (the rightmost such value), then reverse the tail so it becomes ascending, which is its smallest arrangement. If no such i exists, the whole array is descending: reverse all of it.

  1. i = n - 2; while i >= 0 and nums[i] >= nums[i + 1], decrease i.
  2. If i >= 0: j = n - 1; while nums[j] <= nums[i], decrease j; swap nums[i] and nums[j].
  3. Reverse nums[i + 1 .. n - 1].
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--;
            swap(nums, i, j);
        }
        for (int l = i + 1, r = n - 1; l < r; l++, r--) swap(nums, l, r);
    }

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

Edge cases to test

  • A single element: the array stays the same
  • A fully descending array wraps around to fully ascending
  • Duplicate values, like [1, 5, 1] or [2, 2, 2]
  • Only the last two elements need to swap, like [1, 2, 3]

Hints

Hint 1

Look at the array from the right. A descending tail is already as large as it can be, so it cannot be changed alone.

Hint 2

Find the first index i from the right with nums[i] < nums[i + 1]. That is the position that must grow.

Hint 3

Swap nums[i] with the smallest value to its right that is larger than it, then make the tail as small as possible by reversing it.

FAQ

What is the best time complexity for Next Permutation?

Optimal (find the pivot, swap, reverse the tail) runs in O(n) time and O(1) extra space. At most three linear passes: find the pivot, find the swap partner, reverse the tail.

Which pattern does Next Permutation use?

It is a arrays & hashing problem that uses the right to left traversal pattern. Other problems with the same pattern: Array Leaders, Product of Array Except Self, Buildings With an Ocean View.

Is there a brute force solution for Next Permutation?

Yes. Brute force (try every arrangement) takes O(n! · n) time and O(n) space. Generate every arrangement of the values.

Which edge cases should I test for Next Permutation?

A single element: the array stays the same; A fully descending array wraps around to fully ascending; Duplicate values, like [1, 5, 1] or [2, 2, 2]; Only the last two elements need to swap, like [1, 2, 3].