Permutations iv

Array Math Combinatorics Enumeration

34.0% acceptance

Feb 25, 2026

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn permute(n: i32, k: i64) -> Vec<i32> {
    let n = n as usize;
    let n_odds = (n + 1) / 2;
    let n_evens = n / 2;

    // count(last_odd, o, e) = number of alternating perms of o odds + e evens remaining, last was odd/even
    let mut memo = std::collections::HashMap::new();
    fn count(last_odd: bool, o: usize, e: usize, memo: &mut std::collections::HashMap<(bool,usize,usize),i64>) -> i64 {
      if o + e == 0 { return 1; }
      if let Some(&v) = memo.get(&(last_odd, o, e)) { return v; }
      let v: i64 = if last_odd {
        if e == 0 { 0 } else { (e as i64).saturating_mul(count(false, o, e-1, memo)) }
      } else {
        if o == 0 { 0 } else { (o as i64).saturating_mul(count(true, o-1, e, memo)) }
      }.min(i64::MAX / 2);
      memo.insert((last_odd, o, e), v);
      v
    }

    // Total number of alternating permutations
    let total = if n_odds > 0 {
      (n_odds as i64).saturating_mul(count(true, n_odds-1, n_evens, &mut memo))
        .saturating_add((n_evens as i64).saturating_mul(count(false, n_odds, n_evens.saturating_sub(1), &mut memo)))
    } else {
      (n_evens as i64).saturating_mul(count(false, 0, n_evens-1, &mut memo))
    };
    if k > total { return vec![]; }

    let mut result = Vec::new();
    let mut used = vec![false; n + 1]; // used[v] = whether value v is used
    let mut rem_o = n_odds;
    let mut rem_e = n_evens;
    let mut last_odd: Option<bool> = None;
    let mut k = k;

    for _ in 0..n {
      let mut chosen = 0i32;
      for v in 1..=n as i32 {
        if used[v as usize] { continue; }
        let v_is_odd = v % 2 == 1;
        if let Some(lo) = last_odd { if v_is_odd == lo { continue; } }
        let new_o = if v_is_odd { rem_o - 1 } else { rem_o };
        let new_e = if v_is_odd { rem_e } else { rem_e - 1 };
        let c = count(v_is_odd, new_o, new_e, &mut memo);
        if k <= c {
          chosen = v;
          break;
        }
        k -= c;
      }
      if chosen == 0 { return vec![]; }
      result.push(chosen);
      used[chosen as usize] = true;
      let v_is_odd = chosen % 2 == 1;
      if v_is_odd { rem_o -= 1; } else { rem_e -= 1; }
      last_odd = Some(v_is_odd);
    }
    result
  }
}