🔥🔥🔥 Easy Python Solution with Video 🔥🔥🔥
I made a video explaining this problem's intuition and code in details, you can click on my profile and there is my Youtube channel linked ;)Code
I made a video explaining this problem's intuition and code in details, you can click on my profile and there is my Youtube channel linked ;)

# Code
```python3 []
class Solution:
    def permute(self, n: int, k: int) -> List[int]:
        if n % 2:
            # 1 2 3 4 5
            return self.permute_rec(n, k, [i for i in range(1, n+1)], True, False)
        else:
            # 1 2 3 4
            return self.permute_rec(n, k, [i for i in range(1, n+1)], True, True)
    
    def permute_rec(self, n: int, k: int, left_over_numbers: list[int], can_use_odd: bool, can_use_even: bool):
        if n == 0:
            return []
        # un => number of alternating permutations of length n with n//2 odd numbers and n//2 even numbers (n%2==0)
        # vn => number of alternating permutations of length n with n//2 odd numbers and n//2 + 1 even numbers (n%2==1)
        # wn => number of alternating permutations of length n with n//2 + 1 odd numbers and n//2 even numbers (n%2==1)

        # Recursive relation:
        # un = n//2 * vn-1 + n//2 * wn-1
        # vn = (n//2 + 1) * (un-1 // 2)
        # wn = (n//2 + 1) * (un-1 // 2)

        u: list[int] = [0 for _ in range(n+1)]
        u[0] = 2
        v: list[int] = [0 for _ in range(n+1)]
        w: list[int] = [0 for _ in range(n+1)]
        
        for i in range(1, n+1):
            if i % 2:
                # if i is odd
                v[i] = (i // 2 + 1) * (u[i-1] // 2)
                w[i] = (i // 2 + 1) * (u[i-1] // 2)
            else:
                # if i is even
                u[i] = i // 2 * v[i-1] + i // 2 * w[i-1]

        if n % 2:
            # if n is odd
            if k > w[n]:
                return []
        else:
            # if n is even
            if k > u[n]:
                return []
        
        if n % 2:
            # if n is odd
            bucket_size: int = w[n] // (n // 2 + 1)
            bucket: int = (k - 1) // bucket_size
            bucket_copy: int = bucket
            prefix_number = -1
            for i in range(len(left_over_numbers)):
                if left_over_numbers[i] % 2 and can_use_odd:
                    bucket_copy -= 1
                    if bucket_copy == -1:
                        prefix_number = left_over_numbers[i]
                        break
                if left_over_numbers[i] % 2 == 0 and can_use_even:
                    bucket_copy -= 1
                    if bucket_copy == -1:
                        prefix_number = left_over_numbers[i]
                        break
            assert prefix_number != -1
            left_over_numbers.remove(prefix_number)  # O(n)
            return [prefix_number] + self.permute_rec(
                n - 1,
                k - bucket * bucket_size,
                left_over_numbers,
                prefix_number % 2 == 0,
                prefix_number % 2 == 1
            )
        else:
            # if n is even
            bucket_size: int = u[n] // n
            bucket: int = (k - 1) // bucket_size
            bucket_copy: int = bucket
            prefix_number = -1
            for i in range(len(left_over_numbers)):
                if left_over_numbers[i] % 2 and can_use_odd:
                    bucket_copy -= 1
                    if bucket_copy == -1:
                        prefix_number = left_over_numbers[i]
                        break
                if left_over_numbers[i] % 2 == 0 and can_use_even:
                    bucket_copy -= 1
                    if bucket_copy == -1:
                        prefix_number = left_over_numbers[i]
                        break
            assert prefix_number != -1
            left_over_numbers.remove(prefix_number)  # O(n)
            return [prefix_number] + self.permute_rec(
                n - 1,
                k - bucket * bucket_size,
                left_over_numbers,
                prefix_number % 2 == 0,
                prefix_number % 2 == 1
            )
            
            
```
['Python3']