Next Permutation

The problem, simply

You get an array of numbers. Think of every way to order those same numbers, sorted like words in a dictionary: compare the first number, then the second, and so on. Change the array, in place, into the order that comes right after it in that list.

If the array is already the last order (all numbers going down), wrap around to the first order: sorted going up.

A story to remember it

Picture it

Examples

Way 1: the simple way

Make every order of the numbers, sort them, find the current one, and take the one after it (or the first one if the current is last).

class Solution {
    public void nextPermutation(int[] nums) {
        TreeSet<List<Integer>> all = new TreeSet<>((a, b) -> {   // dictionary order
            for (int i = 0; i < a.size(); i++) {
                int c = Integer.compare(a.get(i), b.get(i));
                if (c != 0) return c;
            }
            return 0;
        });
        List<Integer> now = new ArrayList<>();
        for (int x : nums) now.add(x);
        build(nums.clone(), 0, all);
        List<Integer> next = all.higher(now);
        if (next == null) next = all.first();       // the last order wraps around
        for (int i = 0; i < nums.length; i++) nums[i] = next.get(i);
    }

    private void build(int[] a, int start, TreeSet<List<Integer>> all) {
        if (start == a.length) {
            List<Integer> p = new ArrayList<>();
            for (int x : a) p.add(x);
            all.add(p);                               // a set drops repeated orders
            return;
        }
        for (int i = start; i < a.length; i++) {
            int t = a[start]; a[start] = a[i]; a[i] = t;
            build(a, start + 1, all);
            t = a[start]; a[start] = a[i]; a[i] = t;   // put it back
        }
    }
}

How long it takes: there are n! orders and each one has n numbers, O(n! * n) (and more for keeping them sorted). Extra room: all of them are stored, O(n! * n). Already for 12 numbers that is hundreds of millions of orders.

Way 2: the clever way

1. Find the dip. Walk i from the second to last index to the left while nums[i] >= nums[i + 1]. Stop at the first nums[i] < nums[i + 1]. Everything right of i is going down.
2. If there is no dip (i < 0), the whole array goes down. Flip it all and stop.
3. Find the swap partner. Walk j from the right end to the left while nums[j] <= nums[i]. The first nums[j] bigger than nums[i] is the smallest one that is bigger, because the tail goes down.
4. Swap nums[i] and nums[j]. The tail still goes down.
5. Flip the tail (i + 1 to the end) so it goes up. That makes it the smallest possible tail.

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;   // find the dip
        if (i >= 0) {
            int j = n - 1;
            while (nums[j] <= nums[i]) j--;              // smallest bigger number in the tail
            swap(nums, i, j);
        }
        reverse(nums, i + 1, n - 1);                     // make the tail as small as possible
    }

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

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

How long it takes: at most three walks over the array, O(n). Extra room: a few indices, O(1). When there is no dip, i is -1 and the flip covers the whole array, which handles the wrap-around for free.

Watch out for

• Sorting the tail instead of flipping it works but costs O(n log n). The tail always goes down, so flipping is enough.
• Do not return a new array. The problem asks you to change nums in place.
• One element or an empty array: i starts below 0, the flip does nothing, and that is correct.

What interviewers ask next

• Previous permutation. Mirror every step: find the first nums[i] > nums[i + 1] from the right, swap with the biggest smaller number in the tail, then flip the tail.
• The k-th permutation of 1..n. Do not step k times. Use the factorial number system: there are (n-1)! orders for each first number, so divide to pick the first number, then repeat.
• Next bigger number with the same digits (for example 534976 gives 536479). It is exactly this algorithm on the digits. Return -1 if there is no dip or if the result does not fit in an int.
• Print all permutations in order. Start from the sorted array and call next permutation until it wraps around. This handles repeated numbers without a set.

Remember this

Grown-up words: an order of the numbers is a permutation, dictionary order is lexicographic order, the going-down tail is the longest non-increasing suffix, and the swap partner is the dip's successor.