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.

// Brute-force (pro-level bad idea)
// int bruteForce(int n, int k) {
//     List<String> perms = allPermutations(n);
//     Collections.sort(perms);
//     return perms.get(k - 1);
// }

🧠 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

• Prep the Pool:
  • Create a list with numbers 1 to n.

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

• Kick off with Zero-Based Math:
  • k = k – 1, because computers.

  k = k - 1;

• For each position:
  • 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 (int i = n; i > 0; i--) {
      blockSize = fact(i-1);
      index = k / blockSize;
      result += pool.get(index);
      pool.remove(index);
      k = k % blockSize;
  }

💻 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.

🧠 Interviewer Brain-Tattoo

“If it feels like O(n!), your answer and their patience both expire in factorial time.”