L18. K-th Permutation Sequence | Leetcode

This chapter explores how to efficiently find the K-th Permutation Sequence of numbers from $1$ to $N$ when arranged in lexicographical order, moving from an expensive brute-force approach to an elegant $O(N^2)$ mathematical pattern-matching solution.

1. Why Do We Need This? (Problem Statement & Status Quo)

Given an integer $N$, we can form a set of numbers from $1$ to $N$ (e.g., for $N=3$, the set is {1, 2, 3}).

• Any set containing $N$ unique numbers will have exactly $N!$ (N factorial) unique permutations.
• When these $N!$ permutations are written out in lexicographical (dictionary) order, our goal is to find and return the exact K-th permutation.

For instance, if $N = 3$, there are $3! = 6$ unique permutations:

1. 1 2 3 (Index 0)
2. 1 3 2 (Index 1)
3. 2 1 3 (Index 2)
4. 2 3 1 (Index 3)
5. 3 1 2 (Index 4)
6. 3 2 1 (Index 5)

If $K = 3$, the 3rd permutation is 2 1 3. If $K = 5$, it is 3 1 2.

2. The Naive Approach: Recursion + Sorting

How It Works

1. Use recursion to generate all $N!$ permutations.
2. Store every generated permutation inside a data structure (like a list of strings or arrays).
3. Sort the data structure lexicographically.
4. Retrieve the K-th permutation at the $K - 1$ index (assuming zero-based indexing).

Why It Fails in Interviews

• Time Complexity: Generating all permutations takes $O(N!)$ time, and making a deep copy of each permutation of length $N$ takes $O(N)$ time, leading to $O(N! \cdot N)$. Sorting all $N!$ permutations takes $O(N! \log(N!))$ time. For large $N$ (e.g., $N=10$ or $20$), $N!$ explodes exponentially, causing Time Limit Exceeded (TLE).
• Interview Signal: When you explain this brute-force approach, the interviewer will immediately point out the factorial time complexity and ask you to optimize it. That is your cue to present the optimal mathematical approach.

3. Core Mental Model: Dividing Permutations Into Blocks

Real-Life Analogy

Think of a dictionary or a telephone directory. If you are looking for a specific name, you don't scan every single page one by one (brute force). Instead, you look at the first letter, jump straight to the section where names start with that letter, and then repeat the process for the second letter.

Mathematical Breakdown for $N = 4$ ($K = 17$)

When $N = 4$, our set is {1, 2, 3, 4} and there are $4! = 24$ total permutations. We can split these 24 permutations into 4 major blocks based on which number the permutation starts with:

Why 6 permutations per block? Once you fix the first number (e.g., 3), you are left with $3$ remaining numbers ({1, 2, 4}). Those $3$ numbers can permute among themselves in $3! = 6$ ways.

4. Zero-Based Indexing & Finding the First Digit

To align smoothly with computer memory and modulo arithmetic, we convert the 1-based $K$ into a 0-based index:

• If the user asks for the 17th permutation ($K = 17$), we look for the 16th index ($K = 16$).

Now, let's find which block our 16th index falls into:

• Each block contains 6 permutations.
• We divide $K$ by the size of each block: $16 / 6 = 2$ (integer division).
• Looking at our available numbers list [1, 2, 3, 4] (indices 0, 1, 2, 3), the element at index 2 is 3.

Thus, our permutation must start with 3.

5. Step-by-Step Evolution of the Algorithm

Having locked in our first digit (3), the problem shrinks:

• Remaining numbers: {1, 2, 4}
• Remaining index to find: $16 \pmod 6 = 4$ (We need the 4th sequence out of the 6 sequences in that block).

Step 2: Finding the Second Digit

Now we examine permutations of the remaining 3 numbers ({1, 2, 4}) split into blocks of $2! = 2$ permutations:

• We need the 4th sequence (index 4).
• Divide $K$ by block size: $4 / 2 = 2$.
• Looking at our current numbers list [1, 2, 4] at index 2, we pick 4.
• Next $K$: $4 \pmod 2 = 0$.
• Current Answer so far: 34
• Remaining numbers: {1, 2}

Step 3: Finding the Third Digit

Remaining numbers: [1, 2]. Block size = $1! = 1$.

• $K = 0$.
• $0 / 1 = 0$.
• Element at index 0 of [1, 2] is 1.
• Next $K$: $0 \pmod 1 = 0$.
• Current Answer so far: 341
• Remaining numbers: {2}

Step 4: Final Digit

Remaining numbers: [2]. Block size = $0! = 1$.

• $K = 0$.
• $0 / 1 = 0$.
• Element at index 0 of [2] is 2.
• Final Answer: 3412

6. Complete Flow Walkthrough ($N = 4, K = 17 \rightarrow \text{Index } 16$)

7. Reference Implementations

C++ Implementation

#include <bits/stdc++.h>
using class std;

string getPermutation(int n, int k) {
    int fact = 1;
    vector<int> numbers;
    
    // Step 1: Compute (n-1)! and populate numbers list [1, 2, ..., n]
    for (int i = 1; i < n; i++) {
        fact = fact * i;
        numbers.push_back(i);
    }
    numbers.push_back(n);
    
    // Convert to 0-based indexing
    k = k - 1;
    string ans = "";
    
    while (true) {
        // Pick the number at index (k / fact)
        ans += to_string(numbers[k / fact]);
        // Remove the picked number from the list
        numbers.erase(numbers.begin() + (k / fact));
        
        // If no numbers are left, break out of the loop
        if (numbers.size() == 0) {
            break;
        }
        
        // Update k and factorial for the next block size
        k = k % fact;
        fact = fact / numbers.size();
    }
    
    return ans;
}

Java Implementation

import java.util.ArrayList;
import java.util.List;

class Solution {
    public String getPermutation(int n, int k) {
        int fact = 1;
        List<Integer> numbers = new ArrayList<>();
        
        // Step 1: Compute (n-1)! and populate numbers list [1, 2, ..., n]
        for (int i = 1; i < n; i++) {
            fact = fact * i;
            numbers.add(i);
        }
        numbers.add(n);
        
        // Convert to 0-based indexing
        k = k - 1;
        String ans = "";
        
        while (true) {
            // Pick the number at index (k / fact)
            ans += numbers.get(k / fact);
            // Remove the picked number from the list
            numbers.remove(k / fact);
            
            // If no numbers are left, break out of the loop
            if (numbers.size() == 0) {
                break;
            }
            
            // Update k and factorial for the next block size
            k = k % fact;
            fact = fact / numbers.size();
        }
        
        return ans;
    }
}

8. Complexity Analysis

Summary and Key Takeaways

• Avoid Brute Force: Generating all $N!$ permutations via recursion and sorting is extremely inefficient and will result in Time Limit Errors for larger values of $N$.
• Lexicographical Grouping: Permutations of $N$ numbers can be partitioned into $N$ distinct blocks of $(N-1)!$ size based on their starting digit.
• Zero-Based Indexing Conversion: Always convert the 1-based rank $K$ to 0-based by setting $K = K - 1$ to align with array and list index boundaries.
• Mathematical Division and Modulo: Use k / fact to determine the exact index of the digit to pick, and use k % fact to narrow down the remaining rank within that block.
• Dynamic Shrinking: As each digit is picked and appended to the answer, remove it from the available numbers pool and update the factorial block size by dividing by the current remaining list size (fact = fact / numbers.size()).