Permutation Sequence - Video Solutions

Problem Overview: Given n and k, return the k-th permutation of the numbers 1..n in lexicographic order. The challenge is to compute the exact permutation without generating all n! possibilities.

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

This method generates permutations using classic recursion and backtracking. Start with an empty path and repeatedly pick an unused number from 1..n. Each recursive call adds a number to the permutation until the length reaches n. Every complete permutation is produced in lexicographic order if numbers are explored sequentially. Keep a counter and stop once the k-th permutation is reached. This approach is conceptually simple but extremely inefficient because it explores up to n! permutations even though only one result is required.

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

The optimized solution relies on a math observation about permutation groups. For n digits, each leading digit repeats for (n-1)! permutations. Compute factorial values and determine which block the k-th permutation belongs to. Maintain a list of available numbers. The index of the next digit is (k-1) / (n-1)!. Remove that number from the list, append it to the result, update k with the remainder, and repeat for the remaining digits. This effectively converts k into a factorial number system representation. Because removing elements from a list costs O(n), the overall complexity becomes O(n^2). The technique is a common combinatorics trick and often appears alongside backtracking problems as an optimized alternative.

Recommended for interviews: Interviewers expect the factorial-number-system approach. The brute-force backtracking method shows you understand permutation generation, but the mathematical indexing approach demonstrates stronger algorithmic insight and reduces the search from factorial time to quadratic time.