Permutations IV
HardUpdated: Oct 13, 2025
Practice on:
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.
Examples
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 <= 1001 <= k <= 1015
Solution
Method 1 - DP Counting (Combinatorial Construction)
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++
#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
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
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
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
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
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
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 [];
}