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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7
8

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

Examples

Solution

Intuition

We need to generate the k-th lexicographical permutation of [1..n] such that no two adjacent elements are both odd or both even. This is a constrained permutation enumeration problem. Since n can be up to 100 and k can be very large, we must use combinatorial counting and construct the answer digit by digit, skipping over blocks of permutations that do not match the alternating parity constraint.

Approach

We use dynamic programming to count the number of valid alternating permutations for each possible state (remaining odds, remaining evens, last parity). Then, we construct the k-th permutation by choosing the smallest available number at each step whose parity alternates with the previous, and whose block of permutations contains the k-th permutation.

Code

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

ll dp[101][101][2];
ll count(int odd, int even, int last_parity) {
    if (odd + even == 0) return 1;
    ll &res = dp[odd][even][last_parity];
    if (res != -1) return res;
    res = 0;
    if (last_parity == 0 && even > 0) res += count(odd, even-1, 1);
    if (last_parity == 1 && odd > 0) res += count(odd-1, even, 0);
    return res;
}

vector<int> getPermutation(int n, ll k) {
    vector<int> odds, evens;
    for (int i = 1; i <= n; ++i) (i%2 ? odds : evens).push_back(i);
    vector<int> res;
    memset(dp, -1, sizeof(dp));
    for (int first_parity = 0; first_parity < 2; ++first_parity) {
        int odd = odds.size(), even = evens.size();
        if ((first_parity == 0 && even == 0) || (first_parity == 1 && odd == 0)) continue;
        ll cnt = count(odd - (first_parity==1), even - (first_parity==0), first_parity);
        if (k > cnt) { k -= cnt; continue; }
        vector<int> o = odds, e = evens;
        int last = first_parity;
        for (int i = 0; i < n; ++i) {
            vector<int> *pool = (last ? &o : &e);
            sort(pool->begin(), pool->end());
            for (int j = 0; j < pool->size(); ++j) {
                int v = (*pool)[j];
                int no = o.size(), ne = e.size();
                if (last) no--;
                else ne--;
                ll cnt2 = count(no, ne, 1-last);
                if (k > cnt2) { k -= cnt2; continue; }
                res.push_back(v);
                pool->erase(pool->begin() + j);
                last = 1-last;
                break;
            }
        }
        return res;
    }
    return {};
}
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

import "sort"
func getPermutation(n int, k int64) []int {
    var dp [101][101][2]int64
    for i := range dp {
        for j := range dp[i] {
            for l := range dp[i][j] {
                dp[i][j][l] = -1
            }
        }
    }
    var count func(odd, even, last int) int64
    count = func(odd, even, last int) int64 {
        if odd+even == 0 { return 1 }
        if dp[odd][even][last] != -1 { return dp[odd][even][last] }
        res := int64(0)
        if last == 0 && even > 0 { res += count(odd, even-1, 1) }
        if last == 1 && odd > 0 { res += count(odd-1, even, 0) }
        dp[odd][even][last] = res
        return res
    }
    odds, evens := []int{}, []int{}
    for i := 1; i <= n; i++ {
        if i%2 == 1 { odds = append(odds, i) } else { evens = append(evens, i) }
    }
    for first := 0; first < 2; first++ {
        odd, even := len(odds), len(evens)
        if (first == 0 && even == 0) || (first == 1 && odd == 0) { continue }
        var cnt int64
        if first == 0 { cnt = count(odd, even-1, 1) } else { cnt = count(odd-1, even, 0) }
        if k > cnt { k -= cnt; continue }
        res := []int{}
        o, e := append([]int{}, odds...), append([]int{}, evens...)
        last := first
        for i := 0; i < n; i++ {
            pool := &o
            if last == 0 { pool = &e }
            sort.Ints(*pool)
            for j, v := range *pool {
                no, ne := len(o), len(e)
                if last == 1 { no-- } else { ne-- }
                var cnt2 int64
                if last == 1 { cnt2 = count(no, ne, 0) } else { cnt2 = count(no, ne, 1) }
                if k > cnt2 { k -= cnt2; continue }
                res = append(res, v)
                *pool = append((*pool)[:j], (*pool)[j+1:]...)
                last = 1 - last
                break
            }
        }
        return res
    }
    return []int{}
}
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

import java.util.*;
class Solution {
    long[][][] dp = new long[101][101][2];
    long count(int odd, int even, int last) {
        if (odd + even == 0) return 1;
        if (dp[odd][even][last] != -1) return dp[odd][even][last];
        long res = 0;
        if (last == 0 && even > 0) res += count(odd, even-1, 1);
        if (last == 1 && odd > 0) res += count(odd-1, even, 0);
        return dp[odd][even][last] = res;
    }
    public List<Integer> getPermutation(int n, long k) {
        Arrays.stream(dp).forEach(a -> Arrays.stream(a).forEach(b -> Arrays.fill(b, -1)));
        List<Integer> odds = new ArrayList<>(), evens = new ArrayList<>();
        for (int i = 1; i <= n; i++) if (i%2==1) odds.add(i); else evens.add(i);
        for (int first = 0; first < 2; first++) {
            int odd = odds.size(), even = evens.size();
            if ((first == 0 && even == 0) || (first == 1 && odd == 0)) continue;
            long cnt = (first == 0) ? count(odd, even-1, 1) : count(odd-1, even, 0);
            if (k > cnt) { k -= cnt; continue; }
            List<Integer> o = new ArrayList<>(odds), e = new ArrayList<>(evens), res = new ArrayList<>();
            int last = first;
            for (int i = 0; i < n; i++) {
                List<Integer> pool = (last == 1) ? o : e;
                Collections.sort(pool);
                for (int j = 0; j < pool.size(); j++) {
                    int v = pool.get(j);
                    int no = o.size(), ne = e.size();
                    if (last == 1) no--;
                    else ne--;
                    long cnt2 = (last == 1) ? count(no, ne, 0) : count(no, ne, 1);
                    if (k > cnt2) { k -= cnt2; continue; }
                    res.add(v);
                    pool.remove(j);
                    last = 1 - last;
                    break;
                }
            }
            return res;
        }
        return new ArrayList<>();
    }
}
Kotlin
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution {
    private val dp = Array(101) { Array(101) { LongArray(2) { -1L } } }
    private fun count(odd: Int, even: Int, last: Int): Long {
        if (odd + even == 0) return 1L
        if (dp[odd][even][last] != -1L) return dp[odd][even][last]
        var res = 0L
        if (last == 0 && even > 0) res += count(odd, even-1, 1)
        if (last == 1 && odd > 0) res += count(odd-1, even, 0)
        dp[odd][even][last] = res
        return res
    }
    fun getPermutation(n: Int, k: Long): List<Int> {
        for (a in dp) for (b in a) b.fill(-1L)
        val odds = (1..n).filter { it % 2 == 1 }.toMutableList()
        val evens = (1..n).filter { it % 2 == 0 }.toMutableList()
        for (first in 0..1) {
            var odd = odds.size; var even = evens.size
            if ((first == 0 && even == 0) || (first == 1 && odd == 0)) continue
            val cnt = if (first == 0) count(odd, even-1, 1) else count(odd-1, even, 0)
            var k2 = k
            if (k2 > cnt) { k2 -= cnt; continue }
            val o = odds.toMutableList(); val e = evens.toMutableList(); val res = mutableListOf<Int>()
            var last = first
            for (i in 0 until n) {
                val pool = if (last == 1) o else e
                pool.sort()
                for (j in pool.indices) {
                    val v = pool[j]
                    var no = o.size; var ne = e.size
                    if (last == 1) no-- else ne--
                    val cnt2 = if (last == 1) count(no, ne, 0) else count(no, ne, 1)
                    if (k2 > cnt2) { k2 -= cnt2; continue }
                    res.add(v)
                    pool.removeAt(j)
                    last = 1 - last
                    break
                }
            }
            return res
        }
        return emptyList()
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

from functools import lru_cache
def getPermutation(n: int, k: int) -> list[int]:
    odds = [i for i in range(1, n+1) if i%2==1]
    evens = [i for i in range(1, n+1) if i%2==0]
    @lru_cache(maxsize=None)
    def count(odd, even, last):
        if odd + even == 0: return 1
        res = 0
        if last == 0 and even > 0: res += count(odd, even-1, 1)
        if last == 1 and odd > 0: res += count(odd-1, even, 0)
        return res
    for first in [0,1]:
        odd, even = len(odds), len(evens)
        if (first == 0 and even == 0) or (first == 1 and odd == 0): continue
        cnt = count(odd, even-1, 1) if first == 0 else count(odd-1, even, 0)
        if k > cnt: k -= cnt; continue
        o, e = odds[:], evens[:]
        res = []
        last = first
        for _ in range(n):
            pool = o if last else e
            pool.sort()
            for j, v in enumerate(pool):
                no, ne = len(o), len(e)
                if last: no -= 1
                else: ne -= 1
                cnt2 = count(no, ne, 1-last)
                if k > cnt2: k -= cnt2; continue
                res.append(v)
                pool.pop(j)
                last = 1-last
                break
        return res
    return []
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

use std::collections::HashMap;
fn get_permutation(n: usize, mut k: u64) -> Vec<usize> {
    fn count(odd: usize, even: usize, last: usize, memo: &mut HashMap<(usize, usize, usize), u64>) -> u64 {
        if odd + even == 0 { return 1; }
        if let Some(&v) = memo.get(&(odd, even, last)) { return v; }
        let mut res = 0;
        if last == 0 && even > 0 { res += count(odd, even-1, 1, memo); }
        if last == 1 && odd > 0 { res += count(odd-1, even, 0, memo); }
        memo.insert((odd, even, last), res);
        res
    }
    let mut odds: Vec<usize> = (1..=n).filter(|&x| x%2==1).collect();
    let mut evens: Vec<usize> = (1..=n).filter(|&x| x%2==0).collect();
    for first in 0..2 {
        let (odd, even) = (odds.len(), evens.len());
        if (first == 0 && even == 0) || (first == 1 && odd == 0) { continue; }
        let mut memo = HashMap::new();
        let cnt = if first == 0 { count(odd, even-1, 1, &mut memo) } else { count(odd-1, even, 0, &mut memo) };
        if k > cnt { k -= cnt; continue; }
        let (mut o, mut e) = (odds.clone(), evens.clone());
        let mut res = vec![];
        let mut last = first;
        for _ in 0..n {
            let pool = if last == 1 { &mut o } else { &mut e };
            pool.sort();
            for j in 0..pool.len() {
                let v = pool[j];
                let (no, ne) = (o.len(), e.len());
                let (no, ne) = if last == 1 { (no-1, ne) } else { (no, ne-1) };
                let cnt2 = count(no, ne, 1-last, &mut memo);
                if k > cnt2 { k -= cnt2; continue; }
                res.push(v);
                pool.remove(j);
                last = 1-last;
                break;
            }
        }
        return res;
    }
    vec![]
}
TypeScript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

function getPermutation(n: number, k: number): number[] {
    const odds = Array.from({length: n}, (_, i) => i+1).filter(x => x%2===1);
    const evens = Array.from({length: n}, (_, i) => i+1).filter(x => x%2===0);
    const memo = new Map<string, number>();
    function count(odd: number, even: number, last: number): number {
        if (odd + even === 0) return 1;
        const key = `${odd},${even},${last}`;
        if (memo.has(key)) return memo.get(key)!;
        let res = 0;
        if (last === 0 && even > 0) res += count(odd, even-1, 1);
        if (last === 1 && odd > 0) res += count(odd-1, even, 0);
        memo.set(key, res);
        return res;
    }
    for (let first = 0; first < 2; first++) {
        let odd = odds.length, even = evens.length;
        if ((first === 0 && even === 0) || (first === 1 && odd === 0)) continue;
        let cnt = first === 0 ? count(odd, even-1, 1) : count(odd-1, even, 0);
        if (k > cnt) { k -= cnt; continue; }
        let o = odds.slice(), e = evens.slice(), res: number[] = [];
        let last = first;
        for (let i = 0; i < n; i++) {
            let pool = last ? o : e;
            pool.sort((a,b)=>a-b);
            for (let j = 0; j < pool.length; j++) {
                let v = pool[j];
                let no = o.length, ne = e.length;
                if (last) no--;
                else ne--;
                let cnt2 = count(no, ne, 1-last);
                if (k > cnt2) { k -= cnt2; continue; }
                res.push(v);
                pool.splice(j, 1);
                last = 1-last;
                break;
            }
        }
        return res;
    }
    return [];
}

Complexity

  • ⏰ Time complexity: O(n^2) for DP and construction (with memoization, each state is visited once; construction is O(n^2)).
  • 🧺 Space complexity: O(n^2) for DP memoization.