301. Find the K-th Permutation Sequence

Given n and k, consider every permutation of the numbers 1 to n listed in ascending (lexicographic) order. Print the k-th permutation in that list, as a single string with no separators.

Input: The first line contains the integer n. The second line contains the integer k. Output: Print the k-th permutation of 1..n, as a single string of digits with no separators.

1 <= n <= 9, 1 <= k <= n!

Precomputing factorials up to n! ahead of time (rather than recomputing them repeatedly) is a small but useful optimization, since n is small (<=9) but the factorial values are reused at every one of the n positions.

Find the kth permutation of numbers 1 to n, if all permutations were listed in sorted (lexicographic) order. Brute force: Generate all n! permutations in lexicographic order (e.g. using 'next permutation' repeatedly k-1 times starting from the smallest) and read off the kth one directly - this works but costs O(k*n) or more, unnecessarily slow when k could be close to n! for larger n. Optimised: Directly computing which number goes in each position using factorial division (rather than generating and skipping over earlier permutations one at a time) constructs the exact kth permutation in O(n²) (or O(n log n) with a smarter remaining-numbers structure) - a huge improvement over generating up to k-1 earlier permutations first.

Start from the smallest permutation (1, 2, ..., n) and apply the standard 'next lexicographic permutation' step (find the rightmost ascent, swap with the smallest larger element to its right, then reverse the suffix) exactly k - 1 times, printing only the final result. This produces the same answer as generating and storing all permutations, but only the current permutation needs to be kept in memory at any time, since earlier ones are discarded once passed. Time: O(k * n) Space: O(n)

Precompute factorials 0! through (n-1)!. Maintain a list of the still-available digits 1..n. To build each position of the answer from left to right, divide the current (zero-indexed) remaining rank by (n - position - 1)!, use the quotient to pick and remove that index from the list of available digits and append it to the answer, then update the remaining rank to the remainder. This computes the k-th permutation directly in n steps instead of stepping through permutations one at a time, turning a cost proportional to k into one that depends only on n. Time: O(n^2) Space: O(n)

Generate all permutations of 1 to n in lexicographic order (for example via recursive backtracking that tries each unused number in increasing order at each position), and stop once the k-th one generated is reached, printing it. This directly matches the problem's definition of 'k-th in lexicographic order' and is correct, but building and counting through up to k complete permutations, each of length n, is very costly for larger k. Time: O(k * n) Space: O(n!)

1. Notice that exactly (n-1)! permutations share the same FIRST digit - so dividing (k-1) by (n-1)! tells you exactly which remaining number goes first. 2. The REMAINDER of that division carries forward the same logic into choosing the second digit, then the third, and so on. 3. Keep the not-yet-placed numbers in a list, removing the chosen one by its computed index at each step - no actual backtracking or undoing is ever needed, since the factorial arithmetic directly picks the correct branch.

Time: O(n²) - for each of the n positions, computing the factorial division and removing an element from a list (itself O(n) for a plain array) takes O(n), giving O(n²) total. Space: O(n), for the list of not-yet-placed numbers and the resulting permutation string.

Test n = 1 (single permutation '1'), k = 1 and k = n! (first and last permutations), and n = 9 (largest case, 362880 permutations).

Be ready to explain the factorial-division insight clearly with a concrete small example - this direct-construction technique is a hallmark 'clever math trick beats brute enumeration' interview problem.