MediumBacktrackingAI interview only
Permutation Sequence
Asked atgoogleamazonmicrosoftadobe
01 · Problem
Consider all n! orderings of the numbers 1, 2, ..., n, written as strings and listed in increasing lexicographic (dictionary) order. For n = 3 the list is "123", "132", "213", "231", "312", "321".
Given n and k, return the k-th string in this list, counting from k = 1.
02 · Examples
Example 01
Input
n = 3, k = 3
Output
"213"
The ordered list is 123, 132, 213, 231, 312, 321. The third entry is 213.
Example 02
Input
n = 4, k = 9
Output
"2314"
The first 6 permutations start with 1, so the 9th is the 3rd among those that start with 2: 2134, 2143, 2314.
Example 03
Input
n = 3, k = 1
Output
"123"
The very first permutation is the digits in increasing order.
03 · Constraints
- 01`1 <= n <= 9`
- 02`1 <= k <= n!`
- 03`k` is 1-indexed
04 · Optimal complexity
- Time
- O(n^2)
- Space
- O(n)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.