MOST EASY O(N) 
IntuitionThe problem requires finding the k-th lexicographical alternating permutation of the first n natural numbers. Instead of generating all valid permutati


---

# **Intuition**  
The problem requires finding the **k-th lexicographical alternating permutation** of the first `n` natural numbers. Instead of generating all valid permutations, which would be inefficient for large `n`, we use **factorial counting** to determine which elements should be placed in each position.  

An **alternating permutation** ensures that adjacent numbers are never both odd or both even. Given `n`, we calculate the total number of valid permutations and construct the k-th permutation iteratively.

---

# **Approach**  
1. **Precompute Factorials:**  
   - We calculate factorials up to `n` to quickly determine how many valid permutations exist for a given prefix.  



3. **Edge Case:**  
   - If `k > total_valid_count`, return `[]`.

4. **Construct the k-th permutation iteratively:**  
   - Maintain a **list of available numbers** and a **parity state** (`even` or `odd`).  
   - Use **factorials** to skip over blocks of permutations, selecting elements accordingly.  
   - Adjust `k` by subtracting the count of permutations skipped so far.

---

# **Complexity**  
- **Time Complexity:** \(O(n)\) (since we iterate through `n` elements, selecting each in constant time using factorial computations).  
- **Space Complexity:** \(O(n)\) (for storing factorials and available numbers).  

---

# **Code**
```python
from math import factorial
from typing import List

class Solution:
    def permute(self, n: int, k: int) -> List[int]:
        # Step 1: Create a list of numbers from 1 to n
        available_numbers = list(range(1, n + 1))

        # Step 2: Precompute factorials up to n
        fact = [1] * (n + 1)
        for i in range(1, n + 1):
            fact[i] = fact[i - 1] * i

        # Step 3: Compute the total number of valid alternating permutations
        if n % 2 == 0:
            total_valid_permutations = n * fact[(n - 1) // 2] * fact[n // 2]
        else:
            total_valid_permutations = ((n + 1) // 2) * fact[(n - 1) // 2] * fact[n // 2]

        # If k is greater than the total number of valid permutations, return []
        if k > total_valid_permutations:
            return []

        # Step 4: Construct the k-th permutation iteratively
        k -= 1  # Convert to 0-based index
        parity_state = 2 if n % 2 == 0 else 1  # 2 means any number can be selected initially
        result = []

        while available_numbers:
            count_so_far = 0
            for i in range(len(available_numbers)):
                num = available_numbers[i]
                size = len(available_numbers) - 1

                # Only consider numbers maintaining alternating property
                if parity_state == 2 or num % 2 == parity_state:
                    fact_even = fact[size // 2]
                    fact_odd = fact[(size + 1) // 2]
                    valid_permutations = fact_even * fact_odd

                    # If k falls within this range, select this number
                    if k < count_so_far + valid_permutations:
                        parity_state = 1 if num % 2 == 0 else 0  # Switch parity
                        k -= count_so_far  # Reduce k based on skipped permutations
                        result.append(num)
                        available_numbers.pop(i)  # Remove chosen number
                        break
                    else:
                        count_so_far += valid_permutations

        return result
```

---


['Python3']