Minimum obstacle removal to reach corner

Array Breadth-First Search Graph Theory Heap (Priority Queue) Matrix Shortest Path

70.5% acceptance

Feb 25, 2026

1661

You are given a 0-indexed 2D integer array grid of size m x n. Each cell has one of two values: 0 represents an empty cell, 1 represents an obstacle that may be removed. You can move up, down, left, or right from and to an empty cell. Return the minimum number of obstacles to remove so you can move from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1).

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

use std::collections::VecDeque;


impl Solution {
  pub fn minimum_obstacles(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    let mut dist = vec![vec![i32::MAX; n]; m];
    dist[0][0] = 0;
    let mut dq: VecDeque<(usize, usize)> = VecDeque::new();
    dq.push_front((0, 0));
    let dirs = [(0i32, 1i32), (0, -1), (1, 0), (-1, 0)];
    while let Some((r, c)) = dq.pop_front() {
      for (dr, dc) in &dirs {
        let nr = r as i32 + dr;
        let nc = c as i32 + dc;
        if nr < 0 || nr >= m as i32 || nc < 0 || nc >= n as i32 { continue; }
        let nr = nr as usize;
        let nc = nc as usize;
        let cost = dist[r][c] + grid[nr][nc];
        if cost < dist[nr][nc] {
          dist[nr][nc] = cost;
          if grid[nr][nc] == 0 {
            dq.push_front((nr, nc));
          } else {
            dq.push_back((nr, nc));
          }
        }
      }
    }
    dist[m - 1][n - 1]
  }
}