Maximum walls destroyed by robots

Array Binary Search Dynamic Programming Sorting

26.4% acceptance

Feb 25, 2026

There is an endless straight line populated with some robots and walls. You are given integer arrays robots, distance, and walls: robots[i] is the position of the ith robot. distance[i] is the maximum distance the ith robot's bullet can travel. walls[j] is the position of the jth wall. Every robot has one bullet that can either fire to the left or the right at most distance[i] meters. A bullet destroys every wall in its path that lies within its range. Robots are fixed obstacles: if a bullet hits another robot before reaching a wall, it immediately stops at that robot and cannot continue. Return the maximum number of unique walls that can be destroyed by the robots. Notes: A wall and a robot may share the same position; the wall can be destroyed by the robot at that position. Robots are not destroyed by bullets.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_walls(robots: Vec<i32>, distance: Vec<i32>, walls: Vec<i32>) -> i32 {
    let n = robots.len();
    let mut rd: Vec<(i32, i32)> = robots.into_iter().zip(distance.into_iter()).collect();
    rd.sort_unstable_by_key(|&(r, _)| r);
    let robots: Vec<i32> = rd.iter().map(|&(r, _)| r).collect();
    let dist: Vec<i32> = rd.iter().map(|&(_, d)| d).collect();

    let mut walls_sorted = walls;
    walls_sorted.sort_unstable();

    let count = |l: i32, r: i32| -> i32 {
      if l > r { return 0; }
      let lo = walls_sorted.partition_point(|&w| w < l);
      let hi = walls_sorted.partition_point(|&w| w <= r);
      (hi - lo) as i32
    };

    let wall_at = |p: i32| count(p, p);

    // dp[0] = robot fires LEFT, dp[1] = robot fires RIGHT
    let ext_left = count(robots[0] - dist[0], robots[0] - 1);
    let mut dp = [ext_left + wall_at(robots[0]), wall_at(robots[0])];

    if n == 1 {
      let ext_right = count(robots[0] + 1, robots[0] + dist[0]);
      dp[1] += ext_right;
      return dp[0].max(dp[1]);
    }

    for i in 1..n {
      let mut ndp = [i32::MIN; 2];
      let l = robots[i - 1];
      let r = robots[i];
      let right_max_prev = (l + dist[i - 1]).min(r); // blocked by robot[i]
      let left_min_cur = (r - dist[i]).max(l);       // blocked by robot[i-1]

      let ext_right = if i == n - 1 { count(r + 1, r + dist[i]) } else { 0 };

      for prev_dir in 0..2usize {
        for cur_dir in 0..2usize {
          // Count walls in (l, r) covered by this direction combo
          let gap_covered = match (prev_dir, cur_dir) {
            (1, 0) => {
              // prev fires RIGHT, cur fires LEFT: union
              let r_end = right_max_prev.min(r - 1);
              let l_start = left_min_cur.max(l + 1);
              let all = count(l + 1, r - 1);
              let uncovered = count(r_end + 1, l_start - 1);
              all - uncovered
            }
            (1, 1) => count(l + 1, right_max_prev.min(r - 1)),
            (0, 0) => count(left_min_cur.max(l + 1), r - 1),
            (0, 1) => 0,
            _ => unreachable!(),
          };
          let new = gap_covered + wall_at(r) + if cur_dir == 1 { ext_right } else { 0 };
          ndp[cur_dir] = ndp[cur_dir].max(dp[prev_dir] + new);
        }
      }
      dp = ndp;
    }
    dp[0].max(dp[1])
  }
}