60. Permutation Sequence
Take the digits 1, 2, …, n and imagine every possible arrangement of them written out as a string, then the whole collection sorted in lexicographic (dictionary) order. For n = 3 that sorted list is:
123, 132, 213, 231, 312, 321
Write a function that receives two integers n and k and returns the k-th string in that ordering (1-indexed) — without necessarily writing the whole list out, since there are n! of them.
So for n = 3, k = 3 the answer is "213".
Example 1:
Input: n = 3, k = 3
Output: "213"
Explanation: The six arrangements in dictionary order are 123, 132, 213, 231, 312, 321; the 3rd is 213.
Example 2:
Input: n = 4, k = 9
Output: "2314"
Explanation: The 4! = 24 arrangements split into blocks of 3! = 6 by first digit. k = 9 falls in the second block (those starting with 2), and it is the 3rd entry there: 2134, 2143, 2314, …
Example 3:
Input: n = 3, k = 1
Output: "123"
Explanation: k = 1 is the very first arrangement, which is the digits in ascending order.
Constraints:
- 1 ≤ n ≤ 9
- 1 ≤ k ≤ n!
Hints:
Group the n! arrangements by their first digit: each group holds exactly (n-1)! consecutive entries, in order of the leading digit.
So the first digit is determined by which block of size (n-1)! the number k falls into — an integer division. What is left to find inside that block is a smaller instance of the same problem.
Work with k-1 (0-indexed) and a list of unused digits: index = k // (n-1)! picks and removes a digit, k %= (n-1)!, repeat with the remaining digits.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 3, k = 3
Expected output: "213"