Efficient Construction of the K-th Alternating Permutation
IntuitionThe main idea is to construct the k-th alternating permutation without generating all possible permutations. Since an alternating permutation requires
# Intuition
The main idea is to construct the k-th alternating permutation without generating all possible permutations. Since an alternating permutation requires that no two adjacent elements share the same parity, we can leverage this property to count the number of valid completions at each step. This counting helps us “skip” entire blocks of permutations, allowing us to determine the correct candidate for each position based on lexicographical order.

# Approach
1. Dynamic Programming for Counting:
We define a function `dp(o, e, p)` that returns the number of ways to complete the permutation when there are o odd numbers, `e` even numbers left, and the next number must have parity `p` (with `1` for odd and `0` for even).

- If the required parity is odd, there are `o * dp(o-1, e, 0)` completions.
- If even, there are `e * dp(o, e-1, 1)` completions.
- The base case occurs when both `o` and `e` are zero, meaning the permutation is complete.
2. Candidate Selection with Skipping:
For each position in the permutation, we iterate over the candidate numbers in lexicographical order. For each candidate, we calculate the number of permutations ("block size") that would result if we fixed that candidate. If the cumulative count is less than k, we subtract this block size from k and move to the next candidate. When the correct candidate is found (i.e., the k-th permutation lies within its block), we select it, update k accordingly, and remove it from the available numbers.

3. Handling the First Element:

- For odd n, the permutation must start with an odd number.
- For even n, the first element can be either odd or even. We iterate over all candidates in sorted order and determine the appropriate candidate using the same skipping method.
4. Constructing the Permutation:
Once the first element is fixed, the parity requirement alternates for each subsequent position. The above process is repeated until the entire permutation is constructed or it is determined that k exceeds the total number of valid permutations.

# Complexity
- Time complexity:
The dynamic programming function computes O(n²) states, and for each of the n positions, we may iterate over up to O(n) candidates. Thus, the overall time complexity is O(n²).

- Space complexity:
The DP memoization cache requires O(n²) space, and the candidate lists store at most O(n) elements. Therefore, the overall space complexity is O(n²).

# Code
```python3 []
from typing import List
from functools import lru_cache

class Solution:
    def permute(self, n: int, k: int) -> List[int]:
        # dp(o, e, p) returns the number of completions 
        # given that we have o odd numbers and e even numbers left 
        # and the next number must have parity p (1 for odd, 0 for even)
        @lru_cache(maxsize=None)
        def dp(o: int, e: int, p: int) -> int:
            if o == 0 and e == 0:
                return 1
            if p == 1:  # need an odd
                if o == 0:
                    return 0
                return o * dp(o - 1, e, 0)
            else:  # p == 0, need an even
                if e == 0:
                    return 0
                return e * dp(o, e - 1, 1)
        
        # Build available odds and evens
        odds = [x for x in range(1, n + 1) if x % 2 == 1]
        evens = [x for x in range(1, n + 1) if x % 2 == 0]
        result = []
        
        # Helper: Given a fixed expected parity (p) and current available numbers,
        # use "skipping" to choose the candidate.
        # For a state with available odds and evens, if we require parity p:
        # - If p == 1: each candidate (odd) yields a block of size = dp(len(odds)-1, len(evens), 0)
        # - If p == 0: each candidate (even) yields a block of size = dp(len(odds), len(evens)-1, 1)
        def choose_next(expected: int, k: int) -> int:
            if expected == 1:
                candidate_list = odds  # must choose an odd
                if not candidate_list:
                    return -1
                block = dp(len(odds) - 1, len(evens), 0)
            else:
                candidate_list = evens  # must choose an even
                if not candidate_list:
                    return -1
                block = dp(len(odds), len(evens) - 1, 1)
            total = len(candidate_list) * block
            if k > total or block == 0:
                return -1
            # Determine which candidate in candidate_list to choose
            candidate_index = (k - 1) // block
            return candidate_index
        
        # Now, handle the first element.
        # For n odd, the first element must be odd.
        # For n even, we can choose any number, so we iterate over the sorted union.
        if n % 2 == 1:
            # Must start with an odd.
            candidate_list = odds  # already sorted
            block = dp(len(odds) - 1, len(evens), 0)
            total_first = len(candidate_list) * block
            if k > total_first:
                return []
            candidate_index = (k - 1) // block
            candidate = candidate_list[candidate_index]
            result.append(candidate)
            odds.remove(candidate)
            k -= candidate_index * block
            # After choosing an odd, the next expected parity is even (0)
            expected = 0
        else:
            # n is even: free first element (order by actual value)
            available = list(range(1, n + 1))
            available.sort()
            chosen = False
            for candidate in available:
                if candidate % 2 == 1:
                    count = dp(len(odds) - 1, len(evens), 0)
                else:
                    count = dp(len(odds), len(evens) - 1, 1)
                if k > count:
                    k -= count
                else:
                    result.append(candidate)
                    if candidate % 2 == 1:
                        odds.remove(candidate)
                        expected = 0  # next must be even
                    else:
                        evens.remove(candidate)
                        expected = 1  # next must be odd
                    chosen = True
                    break
            if not chosen:
                return []
        
        # Now, build the rest of the permutation.
        # At each step, the required parity is fixed.
        for _ in range(1, n):
            # Depending on the expected parity, select from odds or evens.
            if expected == 1:
                candidate_list = odds
                block = dp(len(odds) - 1, len(evens), 0)
            else:
                candidate_list = evens
                block = dp(len(odds), len(evens) - 1, 1)
            total = len(candidate_list) * block
            if k > total or not candidate_list:
                return []
            candidate_index = (k - 1) // block
            candidate = candidate_list[candidate_index]
            result.append(candidate)
            # Remove the chosen candidate from the corresponding list.
            if expected == 1:
                odds.remove(candidate)
            else:
                evens.remove(candidate)
            k -= candidate_index * block
            # Flip the expected parity.
            expected = 1 - expected
        
        return result

```
['Python3']