☕ DSA Java Articles

Topics › Recursion and Backtracking › Trying out all Combos / Hard

Permutation Sequence

Medium TUF ID 818 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

The numbers 1, 2, ..., n can be arranged in n! different orders. List all of these permutations in lexicographic (dictionary) order and number them from 1. Given n and k, return the k-th permutation as a string of digits.

Constraints: 1 ≤ n ≤ 9, 1 ≤ k ≤ n!. Since 9! = 362 880, every value fits in an int, and the digits are single characters.

Example 1

n = 3: 123, 132, 213, 231, 312, 321
k = 3
answer = "213"

Example 2

n = 4, k = 9
answer = "2314"     // 6 permutations start with 1, so the 9th is the 3rd one starting with 2

Approach 1: Brute force, generate everything and sort

Intuition. The definition says “list all permutations in order and take the k-th”. We can do exactly that: generate every permutation with backtracking, sort the resulting strings, and index into the list.

The swap-based generator fixes one position at a time: for position index, it swaps each candidate digit from index..n-1 into that position, recurses on the rest, and swaps back to undo the choice. It produces every permutation exactly once, but not in lexicographic order (for n = 3 it yields 123, 132, 213, 231, 321, 312), so the sort is required.

Algorithm.

  1. Start from the characters '1'..'n'.
  2. Generate all permutations with the swap recursion, storing each as a string.
  3. Sort the list and return element k - 1.
static String bruteForce(int n, int k) {
    char[] digits = firstPermutation(n);
    List<String> all = new ArrayList<>();
    permute(digits, 0, all);
    Collections.sort(all);                          // swapping does not generate them in order
    return all.get(k - 1);
}

static void permute(char[] digits, int index, List<String> all) {
    if (index == digits.length) {
        all.add(new String(digits));
        return;
    }
    for (int i = index; i < digits.length; i++) {
        swap(digits, index, i);                     // choose digits[i] for this position
        permute(digits, index + 1, all);
        swap(digits, index, i);                     // undo the choice before trying the next one
    }
}

Complexity. Time O(n! × n log(n!)): there are n! strings of length n to build and sort (string comparisons cost up to n). Space O(n! × n) to store them all.

For n = 9 this means building and sorting 362 880 strings. It finishes, but it does an enormous amount of work to read out one answer.

Approach 2: Better, step forward with next permutation

Intuition. We do not need all permutations at once, only the ability to step from one to the next in lexicographic order. That is the classic next permutation algorithm. Start at the smallest permutation 12...n and apply it k - 1 times.

Next permutation works in three moves:

  1. Find the rightmost position i with a[i] < a[i + 1]. Everything to its right is decreasing, which means that suffix is already at its largest arrangement, so position i is the rightmost place where the permutation can still grow.
  2. Swap a[i] with the smallest digit to its right that is larger than a[i]. This increases the prefix by the smallest possible amount.
  3. Reverse the suffix after i, turning it from decreasing into increasing, its smallest arrangement.

Algorithm.

  1. Start from '1'..'n'.
  2. Apply nextPermutation k - 1 times.
  3. Return the result as a string.
static String better(int n, int k) {
    char[] digits = firstPermutation(n);
    for (int step = 1; step < k; step++) nextPermutation(digits);
    return new String(digits);
}

static void nextPermutation(char[] a) {
    int i = a.length - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;         // rightmost position that can still grow
    if (i >= 0) {
        int j = a.length - 1;
        while (a[j] <= a[i]) j--;                   // smallest digit to its right that is larger
        swap(a, i, j);
    }
    reverse(a, i + 1, a.length - 1);                // smallest arrangement of the suffix
}

Complexity. Time O(k × n), which is O(n! × n) when k is close to n!. Space O(n).

Memory is no longer a problem, but the time still grows with k. The optimal method jumps straight to the answer instead of walking there.

Approach 3: Optimal, count blocks of permutations

Intuition. Look at Example 1 again. The six permutations of {1, 2, 3} fall into three blocks of 2! = 2, one block per first digit:

block 0: 123 132      (first digit 1)
block 1: 213 231      (first digit 2)
block 2: 312 321      (first digit 3)

In general, with m digits remaining, the permutations come in m blocks of (m - 1)! each, ordered by their first digit. Convert k to a 0-based rank r = k - 1. Then r / (m - 1)! says how many whole blocks to skip, which identifies the first digit: it is the digit at that index among the remaining digits, in increasing order. The leftover r mod (m - 1)! is the rank inside that block, and the block itself is just “all permutations of the remaining m - 1 digits”. Repeat until no digits remain. (This is writing r in the factorial number system.)

Algorithm.

  1. Put 1..n in a list remaining, and set blockSize = (n - 1)!.
  2. k = k - 1 (0-based rank).
  3. Repeat:
    • index = k / blockSize; remove remaining[index] and append it to the answer.
    • If remaining is empty, stop.
    • k = k mod blockSize; blockSize = blockSize / remaining.size().
  4. Return the answer.
static String optimal(int n, int k) {
    List<Integer> remaining = new ArrayList<>();
    int blockSize = 1;
    for (int i = 1; i <= n; i++) {
        remaining.add(i);
        if (i < n) blockSize *= i;                  // ends as (n - 1)!
    }
    k--;                                            // 0-based rank is easier to divide
    StringBuilder sb = new StringBuilder();
    while (true) {
        int index = k / blockSize;                  // how many whole blocks to skip
        sb.append(remaining.remove(index));
        if (remaining.isEmpty()) break;
        k %= blockSize;                             // rank inside the chosen block
        blockSize /= remaining.size();              // (m - 1)! for the m digits that are left
    }
    return sb.toString();
}

Dry run on Example 2 (n = 4, k = 9, so the 0-based rank is 8):

remaining blockSize rank index = rank / blockSize digit new rank
1 2 3 4 6 8 1 2 2
1 3 4 2 2 1 3 0
1 4 1 0 0 1 0
4 1 0 0 4 done

The answer is "2314". The first row says: skip one block of 6 (the permutations starting with 1), and inside the block of permutations starting with 2, take rank 2.

Complexity. Time O(n^2): n rounds, each removing an element from an ArrayList of at most n items. Space O(n). With n ≤ 9 this is effectively constant. (A Fenwick tree could make the removals O(log n), but that is pointless at this size.)

Edge cases and pitfalls