Permutation Sequence — Solution

Problem

Given n and k, find the k-th lexicographic permutation of the sequence [1, 2, 3, ..., n]. For example, [1, 2, 3] produces six permutations in order: "123", "132", "213", "231", "312", "321".

• Input: n = 3, k = 3
• Output: "213"
• Explanation: The third permutation of [1, 2, 3] in sorted order is "213".

Counter-example: if n = 3 and k = 6, the answer is "321" — the last permutation — showing that k can reach all n! entries.

Intuition

Every group of permutations sharing the same first digit has exactly (n-1)! members. So integer-dividing k by (n-1)! tells us which digit goes first, without listing a single permutation. After placing that digit, the problem reduces to finding the k-remainder-th permutation of the remaining n-1 digits — and the same logic applies again at each position.

Approach 1 — Generate All Permutations

Build every permutation in lexicographic order by backtracking through digits in sorted sequence, then return the one at index k-1.

1. Construct a sorted list of digit strings ["1", "2", ..., "n"]
2. Recursively pick each unused digit in order, appending it to a running sequence
3. When the sequence reaches length n, record it as a complete permutation
4. After all n! permutations are collected, return the entry at index k-1

1def getPermutation(n: int, k: int) -> str:
2    all_perms = []
3
4    def backtrack(remaining: list, current: list):
5        if not remaining:
6            all_perms.append(''.join(current))
7            return
8        for i in range(len(remaining)):
9            current.append(remaining[i])
10            backtrack(remaining[:i] + remaining[i + 1:], current)
11            current.pop()
12
13    backtrack([str(i) for i in range(1, n + 1)], [])
14    return all_perms[k - 1]

Time: O(n! × n) — generating n! permutations each of length n
Space: O(n! × n) — every permutation is stored in memory

Approach 2 — Factorial Number System

Directly compute each digit using division rather than listing anything. Decrement k to 0-indexed first, then at each position divide k by the group size (position-1)! to find which remaining digit belongs there.

1. Build available_digits = [1, 2, ..., n] and precompute factorials[0..n]
2. Decrement k by 1 to make it 0-indexed
3. For each position from n down to 1:
   • group_size = factorials[position - 1] — permutations sharing the same leading digit
   • digit_index = k // group_size — which digit from the remaining list comes next
   • Append available_digits[digit_index] to result and remove it from the list
   • Update k = k % group_size — offset within the chosen group
4. Return the assembled result string

1def getPermutation(n: int, k: int) -> str:
2    import math
3    available_digits = [str(i) for i in range(1, n + 1)]
4    k -= 1  # switch to 0-indexed so integer division is exact at boundaries
5
6    result = []
7    for position in range(n, 0, -1):
8        group_size = math.factorial(position - 1)  # perms per leading digit
9        digit_index = k // group_size
10        result.append(available_digits[digit_index])
11        available_digits.pop(digit_index)
12        k %= group_size  # offset within the group just chosen
13    return ''.join(result)

Time: O(n²) — n positions, each costing O(n) for the list removal
Space: O(n) — the available digits list and factorial array

Complexity Summary

Common Mistakes

• Not converting k to 0-indexed before the loop — the formula k // group_size assumes 0-indexed k; skipping k -= 1 at the start makes the very first digit selection one step too far, cascading errors into every subsequent position
• Using factorial(position) instead of factorial(position - 1) as the group size — each leading digit governs exactly (position-1)! permutations, not position!; using the wrong factorial shifts every index by a factor
• Forgetting to update k with modulo — omitting k %= group_size means subsequent positions see the full original offset rather than the remainder within the chosen group, picking wrong digits from position 2 onward
• Not removing the chosen digit from the available list — after selecting available_digits[digit_index], that digit must be deleted so later positions draw only from the remaining pool; skipping this allows digits to appear twice
• In the brute force, not iterating digits in ascending order — backtracking must always add digits smallest-first (1 → 2 → ... → n) so permutations accumulate in lexicographic order; any other traversal puts the wrong permutation at index k-1

Related Problems

• permutations — generates all permutations rather than targeting one specific index
• next-permutation — advances a given permutation to the next one in lexicographic order
• combinations — enumerates subsets of size k using a comparable counting structure
• palindrome-partitioning — backtracking over all valid arrangements of a string
• subsets — builds every subset with the same backtracking pattern used in the brute force