Permutation Sequence

Description

Permutation Sequence
The set [1, 2, 3, ..., n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Example 1:
Input: n = 3, k = 3
Output: “213”

Example 2:
Input: n = 4, k = 9
Output: “2314”

Example 3:
Input: n = 3, k = 1
Output: “123”

Constraints:

• 1 <= n <= 9
• 1 <= k <= n!

Brute Force Approach: Standard Backtracking (Generate Permutations)

Intuition

Generate all $n!$ permutations in lexicographical order using standard backtracking. Maintain a counter to count up to $k$, and stop as soon as the $k$-th permutation is generated.

import java.util.*;
 
class Solution {
    private int count = 0;
    private String result = "";
 
    public String getPermutation(int n, int k) {
        boolean[] visited = new boolean[n + 1];
        backtrack(n, k, new StringBuilder(), visited);
        return result;
    }
 
    private void backtrack(int n, int k, StringBuilder current, boolean[] visited) {
        if (current.length() == n) {
            count++;
            if (count == k) {
                result = current.toString();
            }
            return;
        }
 
        for (int i = 1; i <= n; i++) {
            if (visited[i]) continue;
 
            visited[i] = true;
            current.append(i);
 
            backtrack(n, k, current, visited);
 
            // Early exit if solution is already found
            if (!result.isEmpty()) return;
 
            // Backtrack
            current.deleteCharAt(current.length() - 1);
            visited[i] = false;
        }
    }
}
 

Complexity

• Time Complexity: $O(k\cdot n)$ — Explores branches sequentially up to the $k$-th permutation. In the worst case ($k=n!$), it takes $O(n!\cdot n)$ time (causes Time Limit Exceeded).
• Space Complexity: $O(n)$ — Auxiliary recursion stack depth and boolean visited array.

---

Most Optimized Solution: Math & Factorial Block Counting (No Backtracking)

Intuition

Instead of generating permutations one by one, we can directly jump to the correct digit at each position using block division.

Permutations are grouped into equal-sized blocks:
For $n=4$ (numbers = [1, 2, 3, 4]):

• Numbers starting with 1 have $(4-1)!=3!=6$ permutations.
• Numbers starting with 2 have $3!=6$ permutations.
• Numbers starting with 3 have $3!=6$ permutations.
• Numbers starting with 4 have $3!=6$ permutations.

If we convert $k$ to 0-based indexing ($k=k-1$):

• Digit Index = $k/(n-1)!$ $\to$ index of the digit to pick from available numbers.
• New $k$ = $k\%(n-1)!$ $\to$ offset within that chosen block.

Pick that digit, remove it from available numbers, update $k$, and repeat for the next position!

Example: n = 4, k = 17  -->  0-based k = 16
Numbers: [1, 2, 3, 4], Block Size = 3! = 6
 
1. Index = 16 / 6 = 2  -->  Pick numbers[2] = '3'. Remainder k = 16 % 6 = 4
   Numbers left: [1, 2, 4], Block Size = 2! = 2
2. Index = 4 / 2 = 2   -->  Pick numbers[2] = '4'. Remainder k = 4 % 2 = 0
   Numbers left: [1, 2], Block Size = 1! = 1
3. Index = 0 / 1 = 0   -->  Pick numbers[0] = '1'. Remainder k = 0 % 1 = 0
   Numbers left: [2], Block Size = 0! = 1
4. Index = 0 / 1 = 0   -->  Pick numbers[0] = '2'.
 
Result = "3412"
 

import java.util.*;
 
class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> numbers = new ArrayList<>();
        int fact = 1;
 
        // Populate numbers list [1, 2, ..., n] and compute (n - 1)!
        for (int i = 1; i < n; i++) {
            fact *= i;
            numbers.add(i);
        }
        numbers.add(n);
 
        // Convert k to 0-based index
        k = k - 1;
 
        StringBuilder sb = new StringBuilder();
 
        while (true) {
            // Pick digit at calculated index
            int index = k / fact;
            sb.append(numbers.get(index));
            numbers.remove(index); // Remove chosen number
 
            if (numbers.isEmpty()) {
                break;
            }
 
            // Update k and decrease block size for next position
            k = k % fact;
            fact = fact / numbers.size();
        }
 
        return sb.toString();
    }
}
 

Complexity

• Time Complexity: $O(n^2)$ — $n$ iterations, with List.remove(index) taking $O(n)$ time. Since $n\le 9$, this runs almost instantaneously.
• Space Complexity: $O(n)$ — Memory to store the numbers list and output string.

---

Easy Memory Rule

“Convert $k$ to 0-based (k--). Digit index is k / (n-1)! and new $k$ is k % (n-1)!.”