The O(n) Club: Permutation Sequence: The Algorithmic VIP Pass

The O(n) Club: Permutation Sequence — The Algorithmic VIP Pass

⚡ TL;DR

Find the k-th permutation (in lex order) of numbers 1 to n… without generating all n! options, because only Indiana Jones loves that kind of adventure.
Brute force: Don’t. It’s O(n!) and your machine is not made of infinite RAM.
Fast way: “Factorial number system” magic. Jump to the permutation you want, like a time traveler who knows the seating chart.

🧠 How Devs Usually Mess This Up

Classic blunder: use next_permutation or recursion to dump all possible permutations into a list, then grab the k-th one. When n hits 9, this approach melts CPUs faster than you can say “heap overflow.” The other top mistake? Classic off-by-one errors—k is 1-based, but every code sample is 0-based. You’ll debug this at 2AM and question your life choices.

🔍 What’s Actually Going On

Here’s the plot: Imagine all n! permutations, sorted. Each choice for your first digit “owns” a block of (n-1)! consecutive permutations. So you pick the right block by dividing (k-1) by (n-1)!. Then, for the next position, repeat with the updated k on the remaining digits. This is called the factorial number system—think of it as an address, but in factorial steps instead of decimal places. You’re not walking the block, you’re riding a zipline to your answer.

🛠️ PseudoCode

Create a list with numbers 1 to n.
k = k – 1, because computers.
block size = factorial(pool.size() – 1)
index = k / block size
append pool.get(index) to result, remove from pool
k = k % block size and keep zipping through the list

For each position:

for (int i = n; i > 0; i--) {
    blockSize = fact(i-1);
    index = k / blockSize;
    result += pool.get(index);
    pool.remove(index);
    k = k % blockSize;
}

Kick off with Zero-Based Math:

k = k - 1;

Prep the Pool:

// List<Integer> pool = [1,2...n]

💻 The Code

public String getPermutation(int n, int k) {
    List<Integer> pool = new ArrayList<>();
    for (int i = 1; i <= n; i++) pool.add(i);
    int[] factorial = new int[n+1];
    factorial[0] = 1;
    for (int i = 1; i <= n; i++) factorial[i] = factorial[i-1] * i;
    k--;
    StringBuilder sb = new StringBuilder();
    for (int i = n; i > 0; i--) {
        int block = factorial[i-1];
        int idx = k / block;
        sb.append(pool.remove(idx));
        k = k % block;
    }
    return sb.toString();
}

⚠️ Pitfalls, Traps & Runtime Smacks

This problem is an off-by-one buffet: Don’t forget k--, unless you like subtle bugs.
Update k after EVERY step: k = k % block. If you don’t, you’ll end up with a shuffle worthy of bad Spotify playlists.
LinkedList vs ArrayList: Removal is O(n) and fine for n ≤ 9, but don’t overthink it.
Time: O(n²) (yes, the remove hurts, but not much for small n)
Space: O(n), so your machine won’t explode.