Minimum reverse operations

Array Hash Table Breadth-First Search Union-Find Ordered Set

16.7% acceptance

Feb 25, 2026

255

You are given an integer n and an integer p representing an array arr of length n where all elements are set to 0's, except position p which is set to 1. You are also given an integer array banned containing restricted positions. Perform the following operation on arr: Reverse a subarray with size k if the single 1 is not set to a position in banned. Return an integer array answer with n results where the ith result is the minimum number of operations needed to bring the single 1 to position i in arr, or -1 if it is impossible.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_reverse_operations(n: i32, p: i32, banned: Vec<i32>, k: i32) -> Vec<i32> {
    let n = n as usize;
    let k = k as usize;
    let p = p as usize;

    let banned_set: std::collections::HashSet<usize> = banned.iter().map(|&x| x as usize).collect();
    let mut ans = vec![-1i32; n];
    ans[p] = 0;

    // Two BTreeSets: one for even-indexed unvisited, one for odd-indexed unvisited
    let mut unvisited: [std::collections::BTreeSet<usize>; 2] = [
      std::collections::BTreeSet::new(),
      std::collections::BTreeSet::new(),
    ];
    for i in 0..n {
      if i != p && !banned_set.contains(&i) {
        unvisited[i % 2].insert(i);
      }
    }

    let mut queue = std::collections::VecDeque::new();
    queue.push_back(p);

    while let Some(pos) = queue.pop_front() {
      // From position pos, reversing subarray [l, l+k-1] containing pos
      // l ranges: max(0, pos+1-k) <= l <= min(n-k, pos)
      let l_min = if pos + 1 >= k { pos + 1 - k } else { 0 };
      let l_max = pos.min(n - k);
      // new_pos = l + (l + k - 1) - pos = 2l + k - 1 - pos
      let new_min = 2 * l_min + k - 1 - pos; // = l_min + (l_min + k - 1) - pos but simplified
      let new_max = 2 * l_max + k - 1 - pos;

      // All new positions have parity new_min % 2
      let parity = new_min % 2;
      let set = &mut unvisited[parity];

      // Collect all positions in [new_min, new_max] from the set
      let reachable: Vec<usize> = set.range(new_min..=new_max).copied().collect();
      for &npos in &reachable {
        set.remove(&npos);
        ans[npos] = ans[pos] + 1;
        queue.push_back(npos);
      }
    }

    ans
  }
}