Find the K-th Permutation Sequence of first N natural numbers

The problem, simply

Take the numbers 1 to n. Write down every order they can stand in, sorted like words in a dictionary: 123, 132, 213, and so on. There are n! orders.

Give back the order at position k, counting from 1.

A story to remember it

Picture it

Examples

Way 1: the simple way

Build the orders one by one in dictionary order, and stop at the k-th.

1. At each spot, try the unused numbers from smallest to biggest. This is what makes the order match the dictionary.
2. When all n spots are filled, count one more order.
3. When the count reaches k, save it and stop everything.

class Solution {
    private int count;
    private String answer;

    public String getPermutation(int n, int k) {
        count = 0;
        answer = "";
        build(n, k, new StringBuilder(), new boolean[n + 1]);
        return answer;
    }

    private void build(int n, int k, StringBuilder cur, boolean[] used) {
        if (count >= k) return;                  // already found it
        if (cur.length() == n) {
            count++;
            if (count == k) answer = cur.toString();
            return;
        }
        for (int d = 1; d <= n; d++) {           // smallest first keeps dictionary order
            if (used[d]) continue;
            used[d] = true;
            cur.append(d);
            build(n, k, cur, used);
            cur.deleteCharAt(cur.length() - 1);  // undo
            used[d] = false;
        }
    }
}

How long it takes: when k is near n!, we build almost every order, and each one takes n steps, so O(n * n!). For n = 9 that is fine, but it grows terribly fast. Extra room: the current order, the used marks and the call stack, O(n).

Way 2: the clever way

Do not walk the tree. Jump through it. With m numbers left, each choice for the next spot owns a block of (m - 1)! orders. So dividing tells you which block you are in.

1. Turn k into a count from 0: k = k - 1. Now k is how many orders to skip.
2. Keep a list of numbers not yet used, smallest first.
3. For each spot, with m numbers left: block = (m - 1)!. The index of the next number is k / block. Take that number out of the list and add it to the answer.
4. Keep only the skip inside that block: k = k % block.

import java.util.*;

class Solution {
    public String getPermutation(int n, int k) {
        int[] fact = new int[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;

        List<Integer> left = new ArrayList<>();
        for (int i = 1; i <= n; i++) left.add(i);   // numbers not used yet, smallest first

        k--;                                        // how many orders to skip
        StringBuilder sb = new StringBuilder();
        for (int m = n; m >= 1; m--) {
            int block = fact[m - 1];                // orders per choice at this spot
            int index = k / block;                  // how many whole blocks we skip
            sb.append(left.remove(index));          // take that number out
            k %= block;                             // skip left inside the block
        }
        return sb.toString();
    }
}

How long it takes: n spots, and removing from the list costs up to n each time, so O(n^2). Extra room: the factorials and the list, O(n).

Watch out for

• Forgetting k - 1. With k counted from 1, k / block is off by one at the edges, for example k = 6 in a block of 6.
• Removing by value instead of by index. In Java, left.remove(index) with an int removes by index, which is what we want. With an Integer it removes by value.
• Overflow. 13! does not fit in an int. The usual limit is n <= 9, but say so.

What interviewers ask next

• The reverse: given an order, find its position. For each spot, count the unused numbers smaller than the one there, multiply by (m - 1)!, add them all, then add 1.
• Make it faster than O(n^2) for big n. Keep the unused numbers in a Fenwick tree or an order statistic tree, so "find the index-th unused number" takes O(log n). Total O(n log n).
• What if the numbers have repeats, like 1, 1, 2? Then each different number you could pick owns (m - 1)! / (c1! * c2! * ...) orders, where the c values are how many of each number are left after the pick. Walk the different numbers in order and subtract whole blocks the same way.
• Give the next order after a given one. That is next permutation: find the first dip from the right, swap it with the next bigger number to its right, and reverse the tail.

Remember this

Grown-up words: dictionary order is lexicographic order, the orders are permutations, the groups of size (m - 1)! come from the factorial number system, and the digits k / block form the Lehmer code.