Permutations IV

Hard

#3085Time: 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.

Patterns

Math Combinatorics Enumeration

Data structures

Array

Prompt

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, 2, 3, 4]
[1, 4, 3, 2]
[2, 1, 4, 3]
[2, 3, 4, 1]
[3, 2, 1, 4]
[3, 4, 1, 2] ← 6th permutation
[4, 1, 2, 3]
[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, 2, 3]
[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, 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 <= 10¹⁵

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1// This is a conceptual illustration and is not a feasible solution.2import java.util.*;3 4class Solution {5    public List<Integer> getPermutation(int n, int k) {6        List<List<Integer>> validPerms = new ArrayList<>();7        List<Integer> currentPerm = new ArrayList<>();8        boolean[] used = new boolean[n + 1];9        generatePermutations(n, currentPerm, used, validPerms);10 11        // The validPerms list is already sorted lexicographically if generated in order.12        if (k > validPerms.size()) {13            return new ArrayList<>();14        }15        return validPerms.get(k - 1);16    }17 18    private void generatePermutations(int n, List<Integer> currentPerm, boolean[] used, List<List<Integer>> validPerms) {19        if (currentPerm.size() == n) {20            if (isAlternating(currentPerm)) {21                validPerms.add(new ArrayList<>(currentPerm));22            }23            return;24        }25 26        for (int i = 1; i <= n; i++) {27            if (!used[i]) {28                currentPerm.add(i);29                used[i] = true;30                generatePermutations(n, currentPerm, used, validPerms);31                used[i] = false;32                currentPerm.remove(currentPerm.size() - 1);33            }34        }35    }36 37    private boolean isAlternating(List<Integer> perm) {38        for (int i = 0; i < perm.size() - 1; i++) {39            if ((perm.get(i) % 2) == (perm.get(i + 1) % 2)) {40                return false;41            }42        }43        return true;44    }45}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1// This is a conceptual illustration and is not a feasible solution for the given constraints.2import java.util.*;3 4class Solution {5    List<List<Integer>> validPerms = new ArrayList<>();6 7    public List<Integer> getPermutation(int n, int k) {8        List<Integer> currentPerm = new ArrayList<>();9        boolean[] used = new boolean[n + 1];10        findAlternating(n, k, currentPerm, used);11        12        if (k > validPerms.size()) { // This check is not optimal, k can be large13            return new ArrayList<>();14        }15        // A better way would be to stop after finding k permutations.16        return validPerms.get(k - 1);17    }18 19    private void findAlternating(int n, int k, List<Integer> currentPerm, boolean[] used) {20        if (validPerms.size() >= k) { // Stop early if we have enough21            return;22        }23        if (currentPerm.size() == n) {24            validPerms.add(new ArrayList<>(currentPerm));25            return;26        }27 28        for (int i = 1; i <= n; i++) {29            if (!used[i]) {30                if (currentPerm.isEmpty() || (currentPerm.get(currentPerm.size() - 1) % 2 != i % 2)) {31                    currentPerm.add(i);32                    used[i] = true;33                    findAlternating(n, k, currentPerm, used);34                    used[i] = false;35                    currentPerm.remove(currentPerm.size() - 1);36                }37            }38        }39    }40}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.*;2 3class Solution {4    public int[] alternatingPermutation(int n, long k) {5        long[] fact = new long[n + 1];6        fact[0] = 1;7        // Use k as the cap to prevent overflow. Any value > k is treated as k.8        long cap = k;9        for (int i = 1; i <= n; i++) {10            fact[i] = safeMul(fact[i - 1], i, cap);11        }12 13        List<Integer> odds = new ArrayList<>();14        List<Integer> evens = new ArrayList<>();15        for (int i = 1; i <= n; i++) {16            if (i % 2 != 0) {17                odds.add(i);18            } else {19                evens.add(i);20            }21        }22 23        long oddStartCount = countPerms(odds.size(), evens.size(), true, fact, cap);24        long evenStartCount = countPerms(evens.size(), odds.size(), true, fact, cap);25        long totalPerms = safeAdd(oddStartCount, evenStartCount, cap);26 27        if (k > totalPerms) {28            return new int[0];29        }30 31        k--; // Convert to 0-indexed32 33        int[] result = new int[n];34        boolean lastWasOdd = false; // Doesn't matter for the first element35 36        for (int i = 0; i < n; i++) {37            int oddIdx = 0;38            int evenIdx = 0;39            while (true) {40                boolean tryOdd = false;41                boolean tryEven = false;42 43                // Determine which number to try next to maintain lexicographical order44                if (i == 0) {45                    if (oddIdx < odds.size() && evenIdx < evens.size()) {46                        if (odds.get(oddIdx) < evens.get(evenIdx)) tryOdd = true; else tryEven = true;47                    } else if (oddIdx < odds.size()) tryOdd = true; else tryEven = true;48                } else {49                    if (!lastWasOdd) tryOdd = true; else tryEven = true;50                }51 52                if (tryOdd) {53                    long count = countPerms(odds.size() - 1, evens.size(), false, fact, cap);54                    if (k >= count) {55                        k -= count;56                        oddIdx++;57                    } else {58                        result[i] = odds.remove(oddIdx);59                        lastWasOdd = true;60                        break;61                    }62                } else { // tryEven63                    long count = countPerms(evens.size() - 1, odds.size(), true, fact, cap);64                    if (k >= count) {65                        k -= count;66                        evenIdx++;67                    } else {68                        result[i] = evens.remove(evenIdx);69                        lastWasOdd = false;70                        break;71                    }72                }73            }74        }75        return result;76    }77 78    // Counts permutations of `count1` items of one parity and `count2` of another,79    // where the next item must be of the first parity.80    private long countPerms(int count1, int count2, boolean isCount1Turn, long[] fact, long cap) {81        if (isCount1Turn) { // Permutation must start with an item from the `count1` group82            if (count1 < count2 || count1 > count2 + 1) return 0;83            return safeMul(fact[count1], fact[count2], cap);84        } else { // Permutation must start with an item from the `count2` group85            if (count2 < count1 || count2 > count1 + 1) return 0;86            return safeMul(fact[count1], fact[count2], cap);87        }88    }89 90    private long safeMul(long a, long b, long cap) {91        if (a == 0 || b == 0) return 0;92        if (b > 0 && a > cap / b) return cap;93        return a * b;94    }95 96    private long safeAdd(long a, long b, long cap) {97        if (a >= cap || b >= cap || a + b >= cap) return cap;98        return a + b;99    }100}

Complexity

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.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem