= 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!

Notes

Good questions to ask the interviewer:

What if n is greater than 10. How should multiple digit numbers be represented in string? --> In this case, just concatenate the number to the answer. So if n = 11, k = 1, ans = "1234567891011"
Whats the maximum value of n and k? --> In this case, k will be a positive integer thats less than INT_MAX. n is reasonable enough to make sure the answer does not bloat up a lot.

Solution

Method 1 – Naive (Repeated Next Permutation)

Intuition

The simplest way to find the k-th permutation is to start with the first permutation (sorted order) and repeatedly generate the next permutation k-1 times. This uses the standard next-permutation algorithm.

Approach

Start with the sequence

Related Tags