Permutation Sequence - Solution & Explanation
Problem Statement
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:
"123""132""213""231""312""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 <= 91 <= k <= n!
Approach Overview
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.
Approach 1: Factorial Number System and Decrement Method
This approach leverages the factorial number system, where the number of permutations starting with a particular digit can be determined by the factorial of (n-1). We adjust k for zero-based indexing and deduct permutations as we determine each digit sequentially.
This C solution involves precomputing factorials and maintaining an array of available numbers. We reduce k by dividing and modulo operations to select which number should appear next in the permutation sequence.
Complexity
Time Complexity: O(n^2) due to potential shifts in the numbers array.
Space Complexity: O(n) for storing factorials and numbers.
Approach 2: Recursive Backtracking (Traditional Approach)
This approach generates permutations using a traditional backtracking method, with the goal of finding the k-th permutation without necessarily generating all permutations explicitly.
This C solution uses a recursive backtracking approach to generate permutations, counting them until reaching the desired k-th permutation, which is stored for output.
Complexity
Time Complexity: O(n!) for generating permutations.
Space Complexity: O(n) due to recursion and string storage.
Approach 3: Enumeration
We know that the set [1,2,..n] has a total of n! permutations. If we determine the first digit, the number of permutations that the remaining digits can form is (n-1)!.
Therefore, we enumerate each digit i. If k is greater than the number of permutations after the current position is determined, then we can directly subtract this number; otherwise, it means that we have found the number at the current position.
For each digit i, where 0 leq i < n, the number of permutations that the remaining digits can form is (n-i-1)!, which we denote as fact. The numbers used in the process are recorded in vis.
The time complexity is O(n^2), and the space complexity is O(n).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Factorial Number System and Decrement Method | Time Complexity: O(n^2) due to potential shifts in the numbers array. Space Complexity: O(n) for storing factorials and numbers. |
| Recursive Backtracking (Traditional Approach) | Time Complexity: O(n!) for generating permutations. Space Complexity: O(n) due to recursion and string storage. |
| Enumeration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking (Traditional) | O(n! * n) | O(n) | Useful for understanding permutation generation or when all permutations are required. |
| Factorial Number System and Decrement Method | O(n^2) | O(n) | Best choice when only the k-th permutation is needed without generating all permutations. |
Video Solution
L18. K-th Permutation Sequence | Leetcode • take U forward • 297,477 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Permutation Sequence easy or hard?
Permutation Sequence Python/Java solution
How to solve Permutation Sequence in O(n)?
What is the best approach for Permutation Sequence?
Is Permutation Sequence asked at Google/Amazon/Meta?
What data structure is used in Permutation Sequence?
What is the time complexity of Permutation Sequence?
Ready to solve this problem?
Practice Permutation Sequence with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor