Construct the lexicographically largest valid sequence

Array Backtracking

72.8% acceptance

Feb 25, 2026

1156

182

Given an integer n, find a sequence with elements in the range [1, n] that satisfies all of the following: The integer 1 occurs once in the sequence. Each integer between 2 and n occurs twice in the sequence. For every integer i between 2 and n, the distance between the two occurrences of i is exactly i. Return the lexicographically largest sequence. It is guaranteed that under the given constraints, there is always a solution.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn construct_distanced_sequence(n: i32) -> Vec<i32> {
    let n = n as usize;
    let len = 2 * n - 1;
    let mut result = vec![0; len];
    let mut used = vec![false; n + 1];
    Self::backtrack(&mut result, &mut used, 0, n);
    result
  }

  fn backtrack(result: &mut Vec<i32>, used: &mut Vec<bool>, pos: usize, n: usize) -> bool {
    // Skip filled positions
    let pos = (pos..result.len()).find(|&i| result[i] == 0);
    let pos = match pos {
      Some(p) => p,
      None => return true, // all filled
    };
    // Try placing numbers from n down to 1 (lexicographically largest)
    for num in (1..=n).rev() {
      if used[num] { continue; }
      if num == 1 {
        result[pos] = 1;
        used[1] = true;
        if Self::backtrack(result, used, pos + 1, n) { return true; }
        result[pos] = 0;
        used[1] = false;
      } else {
        let pos2 = pos + num;
        if pos2 < result.len() && result[pos2] == 0 {
          result[pos] = num as i32;
          result[pos2] = num as i32;
          used[num] = true;
          if Self::backtrack(result, used, pos + 1, n) { return true; }
          result[pos] = 0;
          result[pos2] = 0;
          used[num] = false;
        }
      }
    }
    false
  }
}