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!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.
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.
Time Complexity: O(n^2) due to potential shifts in the numbers array.
Space Complexity: O(n) for storing factorials and numbers.
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.
Time Complexity: O(n!) for generating permutations.
Space Complexity: O(n) due to recursion and string storage.
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).
| 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 | — |
| 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. |
L18. K-th Permutation Sequence | Leetcode • take U forward • 282,343 views views
Watch 9 more video solutions →Practice Permutation Sequence with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor