Block placement queries

Array Binary Search Binary Indexed Tree Segment Tree

18.4% acceptance

Feb 24, 2026

147

There exists an infinite number line, with its origin at 0 and extending towards the positive x-axis. You are given a 2D array queries, which contains two types of queries: For a query of type 1, queries[i] = [1, x]. Build an obstacle at distance x from the origin. For a query of type 2, queries[i] = [2, x, sz]. Check if it is possible to place a block of size sz anywhere in the range [0, x] on the line, such that the block entirely lies in the range [0, x]. A block cannot be placed if it intersects with any obstacle, but it may touch it. Return a boolean array results, where results[i] is true if you can place the block.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn get_results(queries: Vec<Vec<i32>>) -> Vec<bool> {
    use std::collections::BTreeSet;
    const MAX: usize = 50001;
    // Segment tree storing max gap. For each obstacle p, seg stores p - prev_obstacle(p).
    // Query max in [0..x] then compare with x - last_obstacle_before_x.
    let mut seg = vec![0i32; MAX * 4];

    fn seg_update(seg: &mut Vec<i32>, node: usize, lo: usize, hi: usize, pos: usize, val: i32) {
      if lo == hi { seg[node] = val; return; }
      let mid = (lo + hi) / 2;
      if pos <= mid { seg_update(seg, node * 2, lo, mid, pos, val); }
      else { seg_update(seg, node * 2 + 1, mid + 1, hi, pos, val); }
      seg[node] = seg[node * 2].max(seg[node * 2 + 1]);
    }

    fn seg_query(seg: &[i32], node: usize, lo: usize, hi: usize, l: usize, r: usize) -> i32 {
      if r < lo || hi < l { return 0; }
      if l <= lo && hi <= r { return seg[node]; }
      let mid = (lo + hi) / 2;
      seg_query(seg, node * 2, lo, mid, l, r).max(seg_query(seg, node * 2 + 1, mid + 1, hi, l, r))
    }

    let mut obstacles = BTreeSet::<i32>::new();
    obstacles.insert(0); // virtual obstacle at origin
    seg_update(&mut seg, 1, 0, MAX - 1, 0, 0);

    let mut results = Vec::new();
    for q in &queries {
      if q[0] == 1 {
        let x = q[1] as usize;
        if obstacles.contains(&(x as i32)) { continue; }
        let prev = *obstacles.range(..x as i32).next_back().unwrap_or(&0);
        let next = obstacles.range(x as i32 + 1..).next().copied();
        obstacles.insert(x as i32);
        seg_update(&mut seg, 1, 0, MAX - 1, x, x as i32 - prev);
        if let Some(nxt) = next {
          seg_update(&mut seg, 1, 0, MAX - 1, nxt as usize, nxt - x as i32);
        }
      } else {
        let x = q[1] as usize;
        let sz = q[2];
        // max gap among obstacles in [0..x] (gaps stored per right-endpoint obstacle)
        let seg_max = seg_query(&seg, 1, 0, MAX - 1, 0, x);
        // also: gap from last obstacle <= x to x itself
        let last = *obstacles.range(..=x as i32).next_back().unwrap_or(&0);
        let max_gap = seg_max.max(x as i32 - last);
        results.push(max_gap >= sz);
      }
    }
    results
  }
}