60. Permutation Sequence
Permutation Sequence (LeetCode 60) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Backtracking Patterns pattern, in the Permutations subpattern.
How to solve Permutation Sequence
Permutation Sequence is a Generate Permutations problem, part of Backtracking Patterns. Generate all permutations using backtracking. Handle duplicates and next permutation.
Work towards the solution in these steps:
- Consider how permutations can be generated using backtracking, and think about the structure of the solution space as a tree of choices.
- Instead of generating all permutations, explore how the order of permutations relates to factorial numbers and how this can guide your selection at each step.
- Try to determine which number should be placed in each position by calculating how many permutations start with a particular digit, using factorials to skip over groups of permutations.
The reference solution runs in O(n^2) time and O(n) space.
The Permutation Sequence solution and editorial walks through the full approach with reference code.
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 <= 9
- 1 <= k <= n!
Topics and companies
Topics: Math, Recursion.
Reported in interviews at Amazon, Adobe.
How to practise Permutation Sequence on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n^2) time and O(n) space.
Open Permutation Sequence in the code editor, or read the Permutation Sequence editorial for a worked solution with its approach and complexity analysis.
Where Permutation Sequence sits in the DSA pattern sheet
Problems related to Permutation Sequence
Other problems that use the same Permutations and Backtracking Patterns techniques:
- Next Permutation — Medium, same subpattern
- Permutations — Medium, same subpattern
- Permutations II — Medium, same subpattern
- Check if Word Can Be Placed In Crossword — Medium, same pattern
- Combinations — Medium, same pattern
- Combination Sum — Medium, same pattern
Permutation Sequence FAQ
What is the LeetCode number of Permutation Sequence?
Permutation Sequence is LeetCode problem 60, rated Hard.
What pattern is used to solve Permutation Sequence?
Permutation Sequence is a Generate Permutations problem. It belongs to the Backtracking Patterns pattern, in the Permutations subpattern.
What is the time complexity of Permutation Sequence?
The reference solution runs in O(n^2) time and O(n) space.
Which companies ask Permutation Sequence?
Permutation Sequence has been reported in interviews at Amazon, Adobe.