Minimum Obstacle Removal to Reach Corner solution and explanation
Google
9 more videos on this problem
Minimum Obstacle Removal to Reach Corner - Leetcode 2290 - PythonNeetCodeIO · 24:52 · 8K views
Minimum Obstacle Removal to Reach Corner I | Using Studied Concept | Leetcode 2290 |codestorywithMIKcodestorywithMIK · 25:58 · 8K views
Minimum Obstacle Removal to Reach Corner | Leetcode 2290Techdose · 16:38 · 2K views
2290. Minimum Obstacle Removal to Reach Corner | !DP | Dijkstras | 0-1 BFS | GraphsAryan Mittal · 26:50 · 2K views
Minimum Obstacle Removal to Reach Corner | Leetcode 2290 | Dijkstra Algorithm | Contest 295 🔥🔥Coding Decoded · 5:47 · 2K views
2290. Minimum Obstacle Removal to Reach Corner (Leetcode Hard)Programming Live with Larry · 8:50 · 1K views
【每日一题】LeetCode 2290. Minimum Obstacle Removal to Reach CornerHuifeng Guan · 24:48 · 684 views
Leetcode Hard 2290 Minimum Obstacle Removal to Reach Corner - Approach DiscussedAlgorithmicIQ · 18:52 · 607 views
Daily Leetcode #1703: Nov 28, 2024 - 2290. Minimum Obstacle Removal to Reach CornerProgramming Live with Larry · 13:45 · 404 views
LeetCode 2290 Minimum Obstacle Removal to Reach Corner | Dijkstra's Algorithm | Google | GraphCode Harmony · 14:52 · 307 views
The problem
You are given a 0-indexed 2D integer array grid of size m x n. Each cell has one of two values:
0represents an empty cell,1represents 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).
Example 1:
Input: grid = [[0,1,1],[1,1,0],[1,1,0]] Output: 2 Explanation: We can remove the obstacles at (0, 1) and (0, 2) to create a path from (0, 0) to (2, 2). It can be shown that we need to remove at least 2 obstacles, so we return 2. Note that there may be other ways to remove 2 obstacles to create a path.
Example 2:
Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]] Output: 0 Explanation: We can move from (0, 0) to (2, 4) without removing any obstacles, so we return 0.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 1052 <= m * n <= 105grid[i][j]is either0or1.grid[0][0] == grid[m - 1][n - 1] == 0
Approach overview
Problem Overview: You start at the top-left cell of a binary grid and want to reach the bottom-right corner. Cells with 0 are free, while 1 represents an obstacle that must be removed before entering. The goal is to reach the destination while removing the minimum number of obstacles.
Approach 1: Dijkstra-like Algorithm (O(m*n log(m*n)) time, O(m*n) space)
This grid can be modeled as a weighted graph where each cell is a node. Moving into a free cell has cost 0, and moving into an obstacle has cost 1 because you must remove it. Use a priority queue to always expand the cell with the smallest accumulated obstacle removals. Maintain a distance matrix storing the minimum removals required to reach each cell. Each step explores the four directions and updates the cost using the classic relaxation step from shortest path algorithms.
The priority queue ensures the smallest removal count is processed first, exactly like Dijkstra’s algorithm on a weighted graph. This approach works reliably for any grid and is easy to reason about during interviews. Complexity is O(m*n log(m*n)) due to heap operations, and space is O(m*n) for the distance matrix and queue.
Approach 2: Dynamic Programming with Monotonic Queue (0-1 BFS) (O(m*n) time, O(m*n) space)
The key observation is that edge weights are only 0 or 1. That allows replacing the heap with a deque using the 0-1 BFS technique. When moving to a free cell (0), push the position to the front of the deque. When moving into an obstacle (1), push it to the back. This ordering guarantees cells with fewer removals are processed first without a priority queue.
You still maintain a distance matrix to avoid revisiting cells with a worse cost. Each cell is processed at most once per optimal distance update, so the total complexity becomes linear in the grid size: O(m*n). This method is a specialized optimization of Breadth-First Search for weighted edges with values 0 or 1 and is common in grid-based graph problems.
Recommended for interviews: Start by explaining the graph interpretation and the Dijkstra-style solution. Interviewers expect candidates to recognize the shortest path formulation. Then point out that weights are only 0 or 1, which enables the optimized 0-1 BFS with a deque. Demonstrating both approaches shows strong understanding of graph algorithms and practical optimization techniques.
Approach 1: Approach 1: Dijkstra-like Algorithm
This approach uses a priority queue (or deque) to implement a modified Dijkstra's algorithm to explore the grid in a way similar to the 0-1 BFS (Breadth-First Search). Here, obstacles count as 'cost', and we try to find the minimum 'cost' path from the top-left corner to the bottom-right corner. We assign a priority based on the number of obstacles removed.
from collections import deque
def minimum_obstacles(grid):
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
m, n = len(grid), len(grid[0])
dist = [[float('inf')] * n for _ in range(m)]
dist[0][0] = 0
dq = deque([(0, 0)])
while dq:
x, y = dq.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n:
cost = dist[x][y] + grid[nx][ny]
if cost < dist[nx][ny]:
dist[nx][ny] = cost
if grid[nx][ny] == 0:
dq.appendleft((nx, ny))
else:
dq.append((nx, ny))
return dist[-1][-1]import java.util.Deque;
import java.util.LinkedList;
class MinimumObstacles {
public int minimumObstacles(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dist = new int[m][n];
for (int[] row : dist)
Arrays.fill(row, Integer.MAX_VALUE);
Deque<int[]> deque = new LinkedList<>();
dist[0][0] = 0;
deque.offerFirst(new int[]{0, 0});
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
while (!deque.isEmpty()) {
int[] current = deque.poll();
int x = current[0], y = current[1];
for (int[] dir : directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
int cost = dist[x][y] + grid[nx][ny];
if (cost < dist[nx][ny]) {
dist[nx][ny] = cost;
if (grid[nx][ny] == 0) {
deque.offerFirst(new int[]{nx, ny});
} else {
deque.offerLast(new int[]{nx, ny});
}
}
}
}
}
return dist[m - 1][n - 1];
}
}#include <bits/stdc++.h>
using namespace std;
int minimumObstacles(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
deque<pair<int, int>> dq;
dist[0][0] = 0;
dq.push_front({0, 0});
vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
while (!dq.empty()) {
auto [x, y] = dq.front(); dq.pop_front();
for (auto& [dx, dy] : directions) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
int cost = dist[x][y] + grid[nx][ny];
if (cost < dist[nx][ny]) {
dist[nx][ny] = cost;
if (grid[nx][ny] == 0) {
dq.push_front({nx, ny});
} else {
dq.push_back({nx, ny});
}
}
}
}
}
return dist[m - 1][n - 1];
}function minimumObstacles(grid) {
const m = grid.length, n = grid[0].length;
const dist = Array.from({ length: m }, () => Array(n).fill(Infinity));
dist[0][0] = 0;
const deque = [];
deque.push([0, 0]);
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
while (deque.length > 0) {
const [x, y] = deque.shift();
for (const [dx, dy] of directions) {
const nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
const cost = dist[x][y] + grid[nx][ny];
if (cost < dist[nx][ny]) {
dist[nx][ny] = cost;
if (grid[nx][ny] === 0) {
deque.unshift([nx, ny]);
} else {
deque.push([nx, ny]);
}
}
}
}
}
return dist[m - 1][n - 1];
}#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 100000
typedef struct {
int x, y, priority;
} Node;
Node queue[MAX];
int front = 0, rear = -1;
void enqueue(Node n) {
queue[++rear] = n;
}
Node dequeue() {
return queue[front++];
}
bool isEmpty() {
return front > rear;
}
int minimumObstacles(int** grid, int gridSize, int* gridColSize) {
int m = gridSize, n = gridColSize[0];
int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int dist[m][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
dist[i][j] = INT_MAX;
}
}
dist[0][0] = 0;
enqueue((Node){0, 0, 0});
while (!isEmpty()) {
Node node = dequeue();
int x = node.x, y = node.y;
for (int i = 0; i < 4; ++i) {
int nx = x + directions[i][0];
int ny = y + directions[i][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
int cost = dist[x][y] + grid[nx][ny];
if (cost < dist[nx][ny]) {
dist[nx][ny] = cost;
Node newNode = {nx, ny, cost};
if (grid[nx][ny] == 0) {
queue[--front] = newNode;
} else {
enqueue(newNode);
}
}
}
}
}
return dist[m - 1][n - 1];
}using System;
using System.Collections.Generic;
public class MinimumObstacles {
public int MinimumObstaclesInGrid(int[][] grid) {
int m = grid.Length, n = grid[0].Length;
int[][] dist = new int[m][];
for (int i = 0; i < m; i++) {
dist[i] = new int[n];
Array.Fill(dist[i], int.MaxValue);
}
var deque = new LinkedList<(int, int)>();
dist[0][0] = 0;
deque.AddFirst((0, 0));
int[][] directions = { new[] {0, 1}, new[] {1, 0}, new[] {0, -1}, new[] {-1, 0} };
while (deque.Count > 0) {
var current = deque.First.Value;
deque.RemoveFirst();
int x = current.Item1, y = current.Item2;
foreach (var dir in directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
int cost = dist[x][y] + grid[nx][ny];
if (cost < dist[nx][ny]) {
dist[nx][ny] = cost;
if (grid[nx][ny] == 0) {
deque.AddFirst((nx, ny));
} else {
deque.AddLast((nx, ny));
}
}
}
}
}
return dist[m - 1][n - 1];
}
}The function initiates a deque with the starting point (0, 0). We use a distance array to store the minimum number of obstacles needed to reach each cell. Using directions for the four possible moves, we attempt moving to adjacent cells, leveraging the property of a deque to prioritize uncosted moves (moves to a 0) via appendleft. In contrast, costly moves (moves to a 1) are added normally with append. The algorithm continues until the target cell is reached with the minimum obstacle count possible.
Time Complexity: O(m * n)
Space Complexity: O(m * n)
Approach 2: Approach 2: Dynamic Programming with Monotonic Queue
In this approach, we utilize dynamic programming combined with a monotonic queue to solve the problem of reaching the bottom-right corner with minimal obstacle removal. This alternative method involves leveraging the properties of dynamic arrays to store and update minimal removal costs dynamically while using a queue to maintain an effective processing order based on current state values.
from collections import deque
def minimumObstaclesDP(grid):
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
m, n = len(grid), len(grid[0])
dp = [[float('inf')] * n for _ in range(m)]
dp[0][0] = 0
queue = deque([(0, 0)])
while queue:
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n:
cost = dp[x][y] + grid[nx][ny]
if cost < dp[nx][ny]:
dp[nx][ny] = cost
if grid[nx][ny] == 0:
queue.appendleft((nx, ny))
else:
queue.append((nx, ny))
return dp[-1][-1]import java.util.LinkedList;
public class MinimumObstaclesDP {
public int minimumObstaclesDP(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
for (int[] row : dp)
Arrays.fill(row, Integer.MAX_VALUE);
LinkedList<int[]> deque = new LinkedList<>();
dp[0][0] = 0;
deque.offerFirst(new int[]{0, 0});
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
while (!deque.isEmpty()) {
int[] current = deque.poll();
int x = current[0], y = current[1];
for (int[] dir : directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
int cost = dp[x][y] + grid[nx][ny];
if (cost < dp[nx][ny]) {
dp[nx][ny] = cost;
if (grid[nx][ny] == 0) {
deque.offerFirst(new int[]{nx, ny});
} else {
deque.offerLast(new int[]{nx, ny});
}
}
}
}
}
return dp[m - 1][n - 1];
}
}#include <vector>
#include <deque>
using namespace std;
int minimumObstaclesDP(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
dp[0][0] = 0;
deque<pair<int, int>> dq;
dq.push_front({0, 0});
vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
while (!dq.empty()) {
auto [x, y] = dq.front(); dq.pop_front();
for (auto& [dx, dy] : directions) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
int cost = dp[x][y] + grid[nx][ny];
if (cost < dp[nx][ny]) {
dp[nx][ny] = cost;
if (grid[nx][ny] == 0) {
dq.push_front({nx, ny});
} else {
dq.push_back({nx, ny});
}
}
}
}
}
return dp[m - 1][n - 1];
}using System;
using System.Collections.Generic;
public class MinimumObstaclesDP {
public int MinimumObstaclesDPMethod(int[][] grid) {
int m = grid.Length, n = grid[0].Length;
int[][] dp = new int[m][];
for (int i = 0; i < m; i++) {
dp[i] = new int[n];
Array.Fill(dp[i], int.MaxValue);
}
var deque = new LinkedList<(int, int)>();
dp[0][0] = 0;
deque.AddFirst((0, 0));
int[][] directions = { new[] {0, 1}, new[] {1, 0}, new[] {0, -1}, new[] {-1, 0} };
while (deque.Count > 0) {
var current = deque.First.Value;
deque.RemoveFirst();
int x = current.Item1, y = current.Item2;
foreach (var dir in directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
int cost = dp[x][y] + grid[nx][ny];
if (cost < dp[nx][ny]) {
dp[nx][ny] = cost;
if (grid[nx][ny] == 0) {
deque.AddFirst((nx, ny));
} else {
deque.AddLast((nx, ny));
}
}
}
}
}
return dp[m - 1][n - 1];
}
}This dynamic programming version utilizes a monotonic queue to keep the process smooth, in essence maintaining timeline-line transitions amidst evolved states. Adjustments are made based on evaluated costs for obstacles, ensuring ultimately reaching the target state with minimal burdensome path choices.
Time Complexity: O(m * n)
Space Complexity: O(m * n)
Approach 3: Double-Ended Queue BFS
This problem is essentially a shortest path model, but we need to find the minimum number of obstacles to remove.
In an undirected graph with edge weights of only 0 and 1, we can use a double-ended queue to perform BFS. The principle is that if the weight of the current point that can be expanded is 0, it is added to the front of the queue; if the weight is 1, it is added to the back of the queue.
If the weight of an edge is
0, then the newly expanded node has the same weight as the current front node, and it can obviously be used as the starting point for the next expansion.
The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the number of rows and columns of the grid, respectively.
Similar problems:
function minimumObstacles(grid: number[][]): number {
const m = grid.length,
n = grid[0].length;
const dirs = [
[0, 1],
[0, -1],
[1, 0],
[-1, 0],
];
let ans = Array.from({ length: m }, v => new Array(n).fill(Infinity));
ans[0][0] = 0;
let deque = [[0, 0]];
while (deque.length) {
let [x, y] = deque.shift();
for (let [dx, dy] of dirs) {
let [i, j] = [x + dx, y + dy];
if (i < 0 || i > m - 1 || j < 0 || j > n - 1) continue;
const cost = grid[i][j];
if (ans[x][y] + cost >= ans[i][j]) continue;
ans[i][j] = ans[x][y] + cost;
deque.push([i, j]);
}
}
return ans[m - 1][n - 1];
}func minimumObstacles(grid [][]int) int {
m, n := len(grid), len(grid[0])
q := doublylinkedlist.New()
type tuple struct{ i, j, k int }
q.Add(tuple{0, 0, 0})
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
dirs := [5]int{-1, 0, 1, 0, -1}
for {
v, _ := q.Get(0)
p := v.(tuple)
q.Remove(0)
i, j, k := p.i, p.j, p.k
if i == m-1 && j == n-1 {
return k
}
if vis[i][j] {
continue
}
vis[i][j] = true
for h := 0; h < 4; h++ {
x, y := i+dirs[h], j+dirs[h+1]
if x >= 0 && x < m && y >= 0 && y < n {
if grid[x][y] == 0 {
q.Insert(0, tuple{x, y, k})
} else {
q.Add(tuple{x, y, k + 1})
}
}
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Dijkstra-like Algorithm | Time Complexity: O(m * n) |
| Approach 2: Dynamic Programming with Monotonic Queue | Time Complexity: O(m * n) |
| Double-Ended Queue BFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dijkstra-like Algorithm (Priority Queue) | O(m*n log(m*n)) | O(m*n) | General weighted grid problems where edge costs vary and a heap-based shortest path is straightforward. |
| Dynamic Programming with Monotonic Queue (0-1 BFS) | O(m*n) | O(m*n) | Best when edge weights are only 0 or 1, enabling deque-based BFS instead of a priority queue. |
Frequently asked questions
Is Minimum Obstacle Removal to Reach Corner easy or hard?
The problem is classified as Hard on LeetCode because it requires recognizing a shortest path formulation and applying an optimized graph technique. Understanding Dijkstra or 0-1 BFS is necessary to reach the optimal solution.
Minimum Obstacle Removal to Reach Corner Python/Java solution
Implement the solution using either a priority queue (heapq in Python or PriorityQueue in Java) or a deque for 0-1 BFS. The algorithm tracks the minimum obstacles removed while exploring four directions in the grid. Both implementations run in O(m*n log(m*n)) with a heap or O(m*n) with a deque.
How to solve Minimum Obstacle Removal to Reach Corner in O(n)?
Treat the grid as a graph and apply 0-1 BFS. Use a deque where moving to a free cell (0) is pushed to the front and moving through an obstacle (1) is pushed to the back. Maintain a distance matrix tracking the minimum obstacles removed to reach each cell. This processes each cell once, giving O(m*n) time.
What is the best approach for Minimum Obstacle Removal to Reach Corner?
The optimal approach is 0-1 BFS using a deque. Since moving into a free cell costs 0 and removing an obstacle costs 1, edges have only two weights. Using a deque lets you process zero-cost moves from the front and cost-1 moves from the back, achieving O(m*n) time with O(m*n) space.
Is Minimum Obstacle Removal to Reach Corner asked at Google/Amazon/Meta?
Grid shortest path problems with weighted edges are commonly asked by companies like Google, Amazon, and Meta. Variants involving BFS, Dijkstra, or 0-1 BFS appear frequently in technical interviews because they test graph modeling and algorithm optimization.
What data structure is used in Minimum Obstacle Removal to Reach Corner?
The problem typically uses a priority queue (min-heap) for the Dijkstra-style approach or a deque for the optimized 0-1 BFS solution. Both approaches also maintain a distance matrix to track the minimum number of obstacles removed for each grid cell.
What is the time complexity of Minimum Obstacle Removal to Reach Corner?
The priority queue (Dijkstra-like) solution runs in O(m*n log(m*n)) time because each grid cell may be pushed into a heap. Using the optimized 0-1 BFS approach reduces this to O(m*n) since each cell is processed with constant-time deque operations.