Permutation sequence

Math Recursion

52.2% acceptance

Jan 12, 2026

7224

508

The set [1, 2, 3, ..., n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, we get the following sequence for n = 3: "123" "132" "213" "231" "312" "321" Given n and k, return the kth permutation sequence.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn get_permutation(n: i32, k: i32) -> String {
    let mut numbers: Vec<i32> = (1..=n).collect();
    let mut factorials = vec![1; n as usize];
    
    // Calculate factorials
    for i in 1..n as usize {
      factorials[i] = factorials[i - 1] * i as i32;
    }
    
    let mut k = k - 1; // Convert to 0-indexed
    let mut result = String::new();
    
    for i in (1..=n).rev() {
      let idx = (k / factorials[(i - 1) as usize]) as usize;
      result.push_str(&numbers[idx].to_string());
      numbers.remove(idx);
      k %= factorials[(i - 1) as usize];
    }
    
    result
  }
}