Permutations IV - Solution & Explanation

Problem Overview: You are given n and an index k. The task is to construct the k-th permutation of numbers 1..n that satisfies the required parity ordering constraint (odd and even placement rules). Instead of generating all permutations, you need to enumerate only the valid ones and return the k-th in lexicographic order.

Approach 1: Brute Force Permutation Enumeration (O(n! * n) time, O(n) space)

Generate every permutation of 1..n using backtracking or next_permutation. For each permutation, check whether the parity condition holds (for example, alternating odd/even positions). Maintain a counter of valid permutations and stop once the k-th valid one appears. This approach is easy to implement but extremely slow because the permutation count grows factorially. Even with pruning, the worst‑case time is O(n! * n) since each permutation must be validated.

Approach 2: Combinatorics + Lexicographic Enumeration (O(n^2) time, O(n) space)

Instead of generating permutations explicitly, count how many valid permutations start with a given prefix. Split the numbers into odd and even groups, then determine which type of number must appear at each index according to the parity rule. When constructing the permutation, iterate through the remaining candidates in sorted order. For each candidate, temporarily place it and compute how many valid permutations can be formed with the remaining numbers using combinatorial counting (factorials of remaining odd/even counts).

If the number of permutations starting with that candidate is less than k, skip the entire block and subtract that count from k. Otherwise, fix that number in the permutation and continue building the next position. This technique avoids generating unnecessary permutations and directly jumps to the correct lexicographic block. Counting relies on simple factorial math and tracking how many odd and even values remain.

This strategy combines combinatorics with controlled enumeration. The array of remaining numbers is updated after each placement, so candidate scanning adds an O(n) factor per position, giving an overall O(n^2) time complexity with O(n) auxiliary space.

Recommended for interviews: The combinatorics counting approach is what interviewers expect. Brute force shows that you understand permutation generation, but it fails scalability. The optimized solution demonstrates stronger reasoning about permutation blocks, factorial counting, and constrained enumeration across an array of remaining values.