RUST GYM Leetcode 1718 Construct the Lexicographically Largest Valid Sequence Rust Solution

1718. Construct the Lexicographically Largest Valid Sequence

Given an integer n, find a sequence 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.

The distance between two numbers on the sequence, a[i] and a[j], is the absolute difference of their indices, |j - i|.

Return the lexicographically largest sequence. It is guaranteed that under the given constraints, there is always a solution.

A sequence a is lexicographically larger than a sequence b (of the same length) if in the first position where a and b differ, sequence a has a number greater than the corresponding number in b. For example, [0,1,9,0] is lexicographically larger than [0,1,5,6] because the first position they differ is at the third number, and 9 is greater than 5.

Example 1:

Input: n = 3
Output: [3,1,2,3,2]
Explanation: [2,3,2,1,3] is also a valid sequence, but [3,1,2,3,2] is the lexicographically largest valid sequence.

Example 2:

Input: n = 5
Output: [5,3,1,4,3,5,2,4,2]

Constraints:

1 <= n <= 20

Rust Solution

struct Solution;

impl Solution {
    fn construct_distanced_sequence(n: i32) -> Vec<i32> {
        let mut nums: Vec<i32> = vec![];
        for i in (2..=n).rev() {
            nums.push(i);
        }
        nums.push(1);
        let n = n as usize;
        let m = 2 * n - 1;
        let mut cur = vec![0; m];
        let mut visited: u32 = (1 << n) - 1;
        Self::dfs(0, &mut cur, &mut visited, &nums, m, n);
        cur
    }

    fn dfs(
        start: usize,
        cur: &mut Vec<i32>,
        visited: &mut u32,
        nums: &[i32],
        m: usize,
        n: usize,
    ) -> bool {
        if start == m {
            true
        } else {
            if cur[start] == 0 {
                for i in 0..n {
                    if 1 << i & *visited != 0 {
                        let distance = nums[i] as usize;
                        if distance == 1 {
                            *visited &= !(1 << i);
                            cur[start] = nums[i];
                            let found = Self::dfs(start + 1, cur, visited, nums, m, n);
                            if found {
                                return true;
                            }
                            cur[start] = 0;
                            *visited |= 1 << i;
                        } else {
                            if start + distance < m && cur[start + distance] == 0 {
                                cur[start] = nums[i];
                                cur[start + distance] = nums[i];
                                *visited &= !(1 << i);
                                let found = Self::dfs(start + 1, cur, visited, nums, m, n);
                                if found {
                                    return true;
                                }
                                cur[start + distance] = 0;
                                cur[start] = 0;
                                *visited |= 1 << i;
                            }
                        }
                    }
                }
                false
            } else {
                Self::dfs(start + 1, cur, visited, nums, m, n)
            }
        }
    }
}

#[test]
fn test() {
    let n = 3;
    let res = vec![3, 1, 2, 3, 2];
    assert_eq!(Solution::construct_distanced_sequence(n), res);
    let n = 5;
    let res = vec![5, 3, 1, 4, 3, 5, 2, 4, 2];
    assert_eq!(Solution::construct_distanced_sequence(n), res);
}

Having problems with this solution? Click here to submit an issue on github.