Permutation Sequence - Solution & Explanation

Problem Overview: Given two integers n and k, return the kth permutation of the numbers from 1 to n when all permutations are ordered lexicographically. Generating all permutations quickly becomes infeasible because the total count is n!.

Approach 1: Recursive Backtracking (Traditional Approach) (Time: O(n! * n), Space: O(n))

This approach generates permutations the same way classic permutation problems are solved using recursion and backtracking. Maintain a boolean array or set to track used numbers, build permutations one digit at a time, and recursively explore the remaining choices. Every time a full permutation of length n is formed, decrement k. When k reaches zero, that permutation is the answer. The downside is obvious: you still explore permutations sequentially until the kth one appears. Since there are n! permutations and building each takes O(n), the total time complexity is O(n! * n). This method is useful for understanding how permutations are constructed but does not scale for larger n.

Approach 2: Factorial Number System and Decrement Method (Time: O(n^2), Space: O(n))

The key observation from math is that permutations follow a predictable block pattern. For example, when n = 4, each first digit repeats for 3! = 6 permutations before changing. This means you can directly compute which digit belongs in each position instead of generating all permutations.

First, build a list containing numbers 1..n and precompute factorial values. Convert k to zero‑based indexing by subtracting 1. For each position, divide k by the factorial of the remaining digits to determine which number to pick from the list. Append that number to the result and remove it from the list. Update k using the remainder and continue with the next position. Each selection narrows the search space by an entire factorial block, effectively skipping thousands of permutations at once.

The algorithm iterates n times, and removing an element from a list costs O(n), resulting in overall O(n^2) time with O(n) space. This method avoids generating permutations entirely and directly constructs the kth permutation using factorial indexing.

Recommended for interviews: Interviewers expect the factorial number system approach. It demonstrates understanding of permutation ordering and mathematical reasoning rather than brute-force generation. Showing the backtracking idea first proves you understand permutation generation, but the factorial-based solution is the optimized answer typically required for a hard problem.