# Permutations IV
**Difficulty:** HARD
[External](https://leetcode.com/problems/permutations-iv)
Canonical: https://scaleengineer.com/dsa/problems/permutations-iv
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
---
## Problem
Given two integers, `n` and `k`, an **alternating permutation** is a permutation of the first `n` positive integers such that no **two** adjacent elements are both odd or both even.

Return the **k-th** **alternating permutation** sorted in _lexicographical order_. If there are fewer than `k` valid **alternating permutations**, return an empty list.

**Example 1:**

**Input:** n = 4, k = 6

**Output:** \[3,4,1,2\]

**Explanation:**

The lexicographically-sorted alternating permutations of `[1, 2, 3, 4]` are:

1. `[1, 2, 3, 4]`
2. `[1, 4, 3, 2]`
3. `[2, 1, 4, 3]`
4. `[2, 3, 4, 1]`
5. `[3, 2, 1, 4]`
6. `[3, 4, 1, 2]` ← 6th permutation
7. `[4, 1, 2, 3]`
8. `[4, 3, 2, 1]`

Since `k = 6`, we return `[3, 4, 1, 2]`.

**Example 2:**

**Input:** n = 3, k = 2

**Output:** \[3,2,1\]

**Explanation:**

The lexicographically-sorted alternating permutations of `[1, 2, 3]` are:

1. `[1, 2, 3]`
2. `[3, 2, 1]` ← 2nd permutation

Since `k = 2`, we return `[3, 2, 1]`.

**Example 3:**

**Input:** n = 2, k = 3

**Output:** \[\]

**Explanation:**

The lexicographically-sorted alternating permutations of `[1, 2]` are:

1. `[1, 2]`
2. `[2, 1]`

There are only 2 alternating permutations, but `k = 3`, which is out of range. Thus, we return an empty list `[]`.

**Constraints:**

* `1 <= n <= 100`
* `1 <= k <= 1015`

# Approaches
## Brute-Force Generation and Filtering
The most straightforward but inefficient approach is to generate every possible permutation of the numbers from 1 to `n`. For each generated permutation, we check if it satisfies the alternating property. We collect all such valid permutations, sort them lexicographically, and then pick the k-th one from the sorted list.
**Time:** O(n! * n). Generating all `n!` permutations takes `O(n! * n)` time, and checking each one takes `O(n)`. This is computationally prohibitive. · **Space:** O(A_n * n), where A_n is the number of alternating permutations. This can be very large.
**Pros:** Simple to understand and implement.
**Cons:** Extremely high time complexity, making it infeasible for `n` greater than about 10.; High space complexity as it needs to store all valid permutations, which can be a very large number.
### Explanation
This method involves a brute-force enumeration of all possibilities. We can use a standard backtracking algorithm to generate all `n!` permutations. For each complete permutation, a simple loop can verify the alternating condition by checking the parity of adjacent elements. The valid permutations are stored. After all permutations have been checked, the list of valid ones is sorted. Finally, we access the k-th element. Given the constraint `n <= 100`, `n!` is astronomically large, so this approach will time out for most of the test cases.

```java
// This is a conceptual illustration and is not a feasible solution.
import java.util.*;

class Solution {
    public List<Integer> getPermutation(int n, int k) {
        List<List<Integer>> validPerms = new ArrayList<>();
        List<Integer> currentPerm = new ArrayList<>();
        boolean[] used = new boolean[n + 1];
        generatePermutations(n, currentPerm, used, validPerms);

        // The validPerms list is already sorted lexicographically if generated in order.
        if (k > validPerms.size()) {
            return new ArrayList<>();
        }
        return validPerms.get(k - 1);
    }

    private void generatePermutations(int n, List<Integer> currentPerm, boolean[] used, List<List<Integer>> validPerms) {
        if (currentPerm.size() == n) {
            if (isAlternating(currentPerm)) {
                validPerms.add(new ArrayList<>(currentPerm));
            }
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!used[i]) {
                currentPerm.add(i);
                used[i] = true;
                generatePermutations(n, currentPerm, used, validPerms);
                used[i] = false;
                currentPerm.remove(currentPerm.size() - 1);
            }
        }
    }

    private boolean isAlternating(List<Integer> perm) {
        for (int i = 0; i < perm.size() - 1; i++) {
            if ((perm.get(i) % 2) == (perm.get(i + 1) % 2)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Generate all permutations of numbers from 1 to `n`.
- For each permutation, write a helper function to check if it is an alternating permutation (i.e., no two adjacent elements have the same parity).
- Store all valid alternating permutations in a list.
- Sort this list lexicographically.
- If `k` is within the bounds of the list's size, return the `(k-1)`-th element.
- Otherwise, return an empty list.

## Backtracking to Generate All Valid Permutations
A slightly improved approach uses backtracking with pruning. Instead of generating all permutations and then filtering, we check the alternating property at each step of the permutation's construction. If adding a number violates the property, we immediately discard that path (prune the search tree). This avoids exploring invalid branches. However, this method still needs to generate and store all valid alternating permutations before finding the k-th one.
**Time:** O(A_n * n), where A_n is the number of alternating permutations. This is still too slow. · **Space:** O(A_n * n), to store all valid permutations.
**Pros:** More efficient than the first approach by avoiding the generation of invalid permutations.
**Cons:** While better than brute-force, it still generates and stores all valid permutations.; The number of alternating permutations can be very large, leading to excessive memory usage and time, especially for larger `n`.
### Explanation
We can define a recursive function, say `findAlternating(currentPerm, usedNumbers)`. In this function, we loop through numbers 1 to `n`. If a number hasn't been used, we check its parity against the last number in `currentPerm`. If it's the first number or if the parities are different, we add it to `currentPerm`, mark it as used, and recurse. When a permutation of length `n` is formed, it's added to a results list. This is more efficient than the pure brute-force method but still impractical because the number of alternating permutations, `A_n`, grows very quickly (e.g., `A_20` is in the trillions), exceeding time and memory limits.

```java
// This is a conceptual illustration and is not a feasible solution for the given constraints.
import java.util.*;

class Solution {
    List<List<Integer>> validPerms = new ArrayList<>();

    public List<Integer> getPermutation(int n, int k) {
        List<Integer> currentPerm = new ArrayList<>();
        boolean[] used = new boolean[n + 1];
        findAlternating(n, k, currentPerm, used);
        
        if (k > validPerms.size()) { // This check is not optimal, k can be large
            return new ArrayList<>();
        }
        // A better way would be to stop after finding k permutations.
        return validPerms.get(k - 1);
    }

    private void findAlternating(int n, int k, List<Integer> currentPerm, boolean[] used) {
        if (validPerms.size() >= k) { // Stop early if we have enough
            return;
        }
        if (currentPerm.size() == n) {
            validPerms.add(new ArrayList<>(currentPerm));
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!used[i]) {
                if (currentPerm.isEmpty() || (currentPerm.get(currentPerm.size() - 1) % 2 != i % 2)) {
                    currentPerm.add(i);
                    used[i] = true;
                    findAlternating(n, k, currentPerm, used);
                    used[i] = false;
                    currentPerm.remove(currentPerm.size() - 1);
                }
            }
        }
    }
}
```
### Algorithm
- Use a backtracking approach to build permutations step-by-step.
- At each step of the recursion, when considering adding a number, check if it maintains the alternating property with the previously added number.
- If it does, proceed with the recursion. If not, prune this path.
- Collect all fully formed valid alternating permutations.
- Since the numbers are tried in increasing order, the resulting list of permutations will be lexicographically sorted.
- Return the `(k-1)`-th permutation from the list. If `k` is too large, return an empty list.

## Constructive Approach with Combinatorics
The most efficient solution involves constructing the k-th permutation directly without generating all possibilities. This is analogous to the standard k-th permutation problem but adapted for the alternating constraint. We determine the numbers of the permutation one by one, from left to right. At each position, we decide which number to place by calculating how many valid alternating permutations would start with that prefix. By comparing `k` with these counts, we can greedily choose the correct number for each position.
**Time:** O(n^3). The main loop runs `n` times. The inner loop can run up to `n` times. Inside, `ArrayList.remove(index)` takes O(n) time. This can be optimized to O(n log n) using a data structure like a Fenwick tree (BIT) to find and remove the k-th available number in O(log n) time. · **Space:** O(n) for storing the lists of available numbers, the result, and the factorials.
**Pros:** Highly efficient and can handle large `n` and `k` within the given constraints.; Does not require storing a large number of permutations, leading to low space complexity.
**Cons:** The logic is more complex than naive approaches.; Implementation requires careful handling of large numbers and indices.
### Explanation
The core idea is to determine each digit of the permutation sequentially. To decide the first digit, we can try placing `1`, then `2`, and so on. For each choice, we calculate how many valid alternating permutations can be formed with the remaining numbers. 

Let's say we have `o` odd numbers and `e` even numbers left. If we need to place an odd number next, the number of ways to form a valid alternating sequence with the remaining `o-1` odd and `e` even numbers (which must start with an even number) is given by a combinatorial formula. An alternating permutation of `o` odds and `e` evens is possible only if `|o - e| <= 1`. The number of ways to arrange them is `o! * e!`. If `o != e`, the starting parity is fixed. If `o == e`, either parity can start, giving `2 * o! * e!` total permutations.

We can define a helper function `countPerms(o, e, nextIsOdd)` that calculates the number of valid permutations given the remaining counts and the required parity of the next number. This count is essentially `fact[o] * fact[e]` if the parity constraints are met (`o` must be `e` or `e+1` if `nextIsOdd` is true, and `e` must be `o` or `o+1` if `nextIsOdd` is false).

Since `k` and the factorial products can be very large, we must handle potential overflows. We can cap all calculations at `k+1`, as we only need to know if a block of permutations is smaller or larger than the current `k`.

The algorithm proceeds as follows: for each position in the permutation, we iterate through the available numbers in increasing order. We check if the number's parity is valid for the current position. If it is, we calculate the number of completions (`count`). If `k >= count`, we skip this block of permutations by setting `k -= count` and trying the next available number. Otherwise, we've found our digit. We place it in the result, remove it from the available pool, and move to the next position with the updated `k`.

```java
import java.util.*;

class Solution {
    public int[] alternatingPermutation(int n, long k) {
        long[] fact = new long[n + 1];
        fact[0] = 1;
        // Use k as the cap to prevent overflow. Any value > k is treated as k.
        long cap = k;
        for (int i = 1; i <= n; i++) {
            fact[i] = safeMul(fact[i - 1], i, cap);
        }

        List<Integer> odds = new ArrayList<>();
        List<Integer> evens = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i % 2 != 0) {
                odds.add(i);
            } else {
                evens.add(i);
            }
        }

        long oddStartCount = countPerms(odds.size(), evens.size(), true, fact, cap);
        long evenStartCount = countPerms(evens.size(), odds.size(), true, fact, cap);
        long totalPerms = safeAdd(oddStartCount, evenStartCount, cap);

        if (k > totalPerms) {
            return new int[0];
        }

        k--; // Convert to 0-indexed

        int[] result = new int[n];
        boolean lastWasOdd = false; // Doesn't matter for the first element

        for (int i = 0; i < n; i++) {
            int oddIdx = 0;
            int evenIdx = 0;
            while (true) {
                boolean tryOdd = false;
                boolean tryEven = false;

                // Determine which number to try next to maintain lexicographical order
                if (i == 0) {
                    if (oddIdx < odds.size() && evenIdx < evens.size()) {
                        if (odds.get(oddIdx) < evens.get(evenIdx)) tryOdd = true; else tryEven = true;
                    } else if (oddIdx < odds.size()) tryOdd = true; else tryEven = true;
                } else {
                    if (!lastWasOdd) tryOdd = true; else tryEven = true;
                }

                if (tryOdd) {
                    long count = countPerms(odds.size() - 1, evens.size(), false, fact, cap);
                    if (k >= count) {
                        k -= count;
                        oddIdx++;
                    } else {
                        result[i] = odds.remove(oddIdx);
                        lastWasOdd = true;
                        break;
                    }
                } else { // tryEven
                    long count = countPerms(evens.size() - 1, odds.size(), true, fact, cap);
                    if (k >= count) {
                        k -= count;
                        evenIdx++;
                    } else {
                        result[i] = evens.remove(evenIdx);
                        lastWasOdd = false;
                        break;
                    }
                }
            }
        }
        return result;
    }

    // Counts permutations of `count1` items of one parity and `count2` of another,
    // where the next item must be of the first parity.
    private long countPerms(int count1, int count2, boolean isCount1Turn, long[] fact, long cap) {
        if (isCount1Turn) { // Permutation must start with an item from the `count1` group
            if (count1 < count2 || count1 > count2 + 1) return 0;
            return safeMul(fact[count1], fact[count2], cap);
        } else { // Permutation must start with an item from the `count2` group
            if (count2 < count1 || count2 > count1 + 1) return 0;
            return safeMul(fact[count1], fact[count2], cap);
        }
    }

    private long safeMul(long a, long b, long cap) {
        if (a == 0 || b == 0) return 0;
        if (b > 0 && a > cap / b) return cap;
        return a * b;
    }

    private long safeAdd(long a, long b, long cap) {
        if (a >= cap || b >= cap || a + b >= cap) return cap;
        return a + b;
    }
}
```
### Algorithm
- **Precomputation:** Calculate factorials up to `n`. Since the results can be large, cap them at a value like `k+1` to prevent overflow, as any count larger than `k` is equivalent for our purpose.
- **Initialization:** Create lists of available odd and even numbers. Convert `k` to be 0-indexed (`k--`).
- **Total Count Check:** Calculate the total number of alternating permutations. If `k` is greater than this total, return an empty list.
- **Constructive Loop:** Iterate from `i = 0` to `n-1` to determine the number at each position of the result array.
  - In each iteration `i`, iterate through the available numbers (both odd and even if `i=0`, or only of the required parity if `i>0`) in increasing lexicographical order.
  - For each candidate number, calculate how many valid alternating permutations can be formed with the remaining numbers. This count is `fact[rem_odds] * fact[rem_evens]`.
  - If `k` is greater than or equal to this count, it means the desired permutation is not in this block. Subtract the count from `k` and try the next available number.
  - If `k` is less than the count, the number for the current position is found. Add it to the result, remove it from the available numbers list, and break the inner loop to proceed to the next position.
- **Return:** Return the constructed permutation.