2290. Minimum Obstacle Removal to Reach Corner
Problem Description
You are given a 2D integer array grid
with two possible values in each cell:
0
represents an empty cell you can move through.1
represents an obstacle that can be removed.
The grid has m
rows and n
columns, and the goal is to move from the top-left corner (0, 0)
to the bottom-right corner (m - 1, n - 1)
. You can move in four directions from an empty cell: up, down, left, or right.
The problem asks you to find the minimum number of obstacles (1
s) that need to be removed to enable this path-finding from the start to the end.
Flowchart Walkthrough
Let's analyze the problem from LeetCode 2290, "Minimum Obstacle Removal to Reach Corner," using the algorithm Flowchart. Here's a step-by-step decomposition:
Is it a graph?
- Yes: The grid can be treated as a graph where each cell is a node, and the movement between cells are the edges.
Is it a tree?
- No: Given the grid layout, it's not specifically a tree as it could contain loops and multiple paths between cells.
Is the problem related to directed acyclic graphs (DAGs)?
- No: The grid allows for movements in multiple directions (not necessarily one-directional or acyclic).
Is the problem related to shortest paths?
- Yes: We are asked to find the minimum number of obstacle removals needed to move from the top-left corner to the bottom-right corner, which is essentially finding the shortest path in terms of obstacle removals.
Is the graph weighted?
- Yes: Since the number of obstacles can vary per cell, and removing these obstacles has a 'cost', this effectively makes the graph weighted where the weights represent the cost (number of obstacles) to move through each cell.
Conclusion: According to the flowchart, for a problem dealing with weighted graphs and shortest paths, we should use Dijkstra's Algorithm. However, since weights are limited (0 or 1 in most cases) and the objective is to find the minimum number, the Breadth-First Search (BFS) with a priority queue can be efficient and is appropriate. Thus, BFS would be a more simplified approach considering the discrete and small range of edge weights (0 or 1). This approach uses BFS to explore the least 'costly' paths first, akin to Dijkstra's algorithm in principle, but adapted to the specific characteristics of the problem's grid and obstacle setup.
Intuition
To solve this problem, we use a breadth-first search (BFS) approach. BFS is a graph traversal method that expands and examines all nodes of a level before moving to the next level. This characteristic makes BFS suitable for finding the shortest path on unweighted graphs, or in this case, to find the minimum number of obstacles to remove.
The idea is to traverse the grid using BFS, keeping track of the position (i, j)
we're currently in and the count k
of obstacles that we have removed to reach this position. Each time we can either move to an adjacent empty cell without incrementing the obstacle removal count or move to an adjacent cell with an obstacle by incrementing the removal count by one.
We use a deque to facilitate the BFS process. When we encounter an empty cell, we add the position to the front of the deque, giving priority to such moves for expansion before those requiring obstacle removal, effectively ensuring the BFS prioritizes paths with fewer obstacles removed.
A visited set vis
is used to keep track of the cells we have already processed to avoid re-processing and potentially getting into cycles.
The search continues until we reach the bottom-right corner (m - 1, n - 1)
, at which point we return the count of removed obstacles k
which represents the minimum number of obstacles that need to be removed.
Learn more about Breadth-First Search, Graph, Shortest Path and Heap (Priority Queue) patterns.
Solution Approach
The provided Python code implements the BFS algorithm using a deque, a double-ended queue that allows the insertion and removal of elements from both the front and the back with constant time complexity O(1)
.
BFS (Breadth-First Search)
At a high level, the BFS algorithm works by visiting all neighbors of a node before moving on to the neighbors' neighbors. It uses a queue to keep track of which nodes to visit next.
Deque for BFS
In the Python code, the deque
is used instead of a regular queue. When the BFS explores a cell with an obstacle (value 1
), it appends the new state to the end of the deque. Conversely, when it explores a cell without an obstacle (value 0
), it appends the new state to the front of the deque.
Implementation Details
- Initialize the deque
q
with a tuple containing the starting position and the initial number of obstacles removed(0, 0, 0)
. - Create a
vis
set to record visited positions and avoid revisiting them. - The
dirs
tuple is used to calculate the adjacent cells' positions with the help of a helper function likepairwise
. - Enter a loop that continues until the end condition is met (reaching
(m - 1, n - 1)
). - Use
popleft
to get the current position and the countk
of the obstacles removed. - If the target position is reached, return
k
. - If the position has been visited before (
(i, j) in vis
), just continue to the next iteration. - Otherwise, mark the position as visited by adding
(i, j)
tovis
. - Iterate over all possible directions, and calculate the adjacent cell positions
(x, y)
. - If
(x, y)
is within the grid bounds and is not an obstacle, append it to the front of the deque with the same number of removed obstaclesk
. - If
(x, y)
has an obstacle, append it to the end of the deque and increment the count of removed obstacles by1
.
This process prioritizes exploring paths with fewer obstacles, and since BFS is used, it guarantees that the first time we reach the bottom-right corner is via the path that requires the minimum number of obstacles to be removed.
The solution effectively mixes BFS traversal with a priority queue concept by using a deque to manage traversal order, ensuring an efficient search for the minimum obstacle removal path.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Suppose we have the following grid
:
grid = [ [0, 1, 0], [0, 1, 1], [0, 0, 0] ]
Here, m = 3
and n = 3
. We want to move from (0, 0)
to (2, 2)
with the minimum number of obstacles removed.
Step-by-Step Process:
-
We start by initializing the deque
q
with the starting position and the initial number of obstacles removed, which is0
. Soq = deque([(0, 0, 0)])
. -
The
vis
set is initialized to ensure we don't visit the same positions repeatedly. In the beginning, it's empty:vis = set()
. -
The BFS begins. We dequeue the first element
(i, j, k) = (0, 0, 0)
, where(i, j)
represents the current cell, andk
is the number of removed obstacles so far. -
We have not reached the target, so we check the adjacent cells:
- Right
(0, 1)
: It has an obstacle. We increment obstacle count and add it to the end ofq
:q = deque([(0, 1, 1)])
. - Down
(1, 0)
: No obstacle. We add it to the front ofq
:q = deque([(1, 0, 0), (0, 1, 1)])
.
- Right
-
We mark the current cell
(0, 0)
as visited:vis.add((0, 0))
. -
Now the deque
q
has cells to process, so we take the one from the front, which is(1, 0, 0)
. -
From
(1, 0)
, we again check the adjacent cells:- Right
(1, 1)
: It has an obstacle, add it to end:q = deque([(0, 1, 1), (1, 1, 1)])
. - Down
(2, 0)
: No obstacle, add it to front:q = deque([(2, 0, 0), (0, 1, 1), (1, 1, 1)])
.
- Right
-
We mark the cell
(1, 0)
as visited:vis.add((1, 0))
. -
The steps repeat, dequeuing from the front, checking adjacent cells, and enqueueing in the deque according to the rules.
-
Eventually, we dequeue the cell
(2, 0, 0)
. From here, we can go right to(2, 1)
with no obstacle and add it to the front:q = deque([(2, 1, 0), (0, 1, 1), (1, 1, 1)])
. -
Again, we mark
(2, 0)
as visited:vis.add((2, 0))
. -
Dequeuing
(2, 1, 0)
, we can go right to the target(2, 2)
with no obstacle. We add it to the front. -
Mark
(2, 1)
as visited and check the next cell fromq
. -
Finally, we reach
(2, 2)
which is the target. We have not needed to remove any obstacles, so we returnk = 0
.
Throughout this process, we have explored paths with the fewest obstacles first, using the deque to effectively prioritize cells without obstacles. By doing this, we've ensured that the first time we reach the end, it is the path with the minimum number of obstacles removed. In this case, no obstacles needed to be removed.
Solution Implementation
1from collections import deque
2from itertools import pairwise # Note: requires Python 3.10+, for earlier versions use a custom pairwise implementation
3
4class Solution:
5 def minimumObstacles(self, grid):
6 # Get the dimensions of the grid
7 rows, cols = len(grid), len(grid[0])
8
9 # Initialize a queue with the starting point and 0 obstacles encountered
10 queue = deque([(0, 0, 0)])
11
12 # Create a set to keep track of visited cells
13 visited = set()
14
15 # Define the directions to move in the grid, pairwise will use this
16 directions = (-1, 0, 1, 0, -1)
17
18 # Loop until we find the exit or run out of cells to explore
19 while queue:
20 # Pop the cell from the queue and count of obstacles encountered so far
21 i, j, obstacle_count = queue.popleft()
22
23 # If we've reached the bottom right corner, return the obstacle count
24 if i == rows - 1 and j == cols - 1:
25 return obstacle_count
26
27 # If this cell has been visited before, skip to the next iteration
28 if (i, j) in visited:
29 continue
30
31 # Mark the current cell as visited
32 visited.add((i, j))
33
34 # Iterate over all possible moves (up, down, left, right)
35 for dx, dy in pairwise(directions):
36 x, y = i + dx, j + dy
37
38 # Check if the new position is within bounds
39 if 0 <= x < rows and 0 <= y < cols:
40 # If there is no obstacle, add the cell to the front of the queue to explore it next
41 if grid[x][y] == 0:
42 queue.appendleft((x, y, obstacle_count))
43 # If there is an obstacle, add the cell to the back of the queue with the obstacle count incremented
44 else:
45 queue.append((x, y, obstacle_count + 1))
46
47# If running Python version earlier than 3.10, define your pairwise function like this:
48# def pairwise(iterable):
49# "s -> (s0,s1), (s1,s2), (s2, s3), ..."
50# a, b = tee(iterable)
51# next(b, None)
52# return zip(a, b)
53
54# Note: The pairwise function returns consecutive pairs of elements from the input.
55# For the directions in this code, it's used to generate the pairs (up, right), (right, down),
56# (down, left), and (left, up) to traverse the grid in a clockwise manner.
57
1class Solution {
2 public int minimumObstacles(int[][] grid) {
3 // Get the dimensions of the grid
4 int rows = grid.length, cols = grid[0].length;
5
6 // Create a deque to hold the positions and the current obstacle count
7 Deque<int[]> queue = new ArrayDeque<>();
8 // Start from the upper left corner (0,0) with 0 obstacles
9 queue.offer(new int[] {0, 0, 0});
10 // Array to iterate over the 4 possible directions (up, right, down, left)
11 int[] directions = {-1, 0, 1, 0, -1};
12 // Visited array to keep track of positions already visited
13 boolean[][] visited = new boolean[rows][cols];
14
15 // Process cells until the queue is empty
16 while (!queue.isEmpty()) {
17 // Poll the current position and the number of obstacles encountered so far
18 int[] position = queue.poll();
19 int currentRow = position[0];
20 int currentCol = position[1];
21 int obstacles = position[2];
22
23 // Check if we have reached the bottom-right corner
24 if (currentRow == rows - 1 && currentCol == cols - 1) {
25 // If we reached the destination, return the number of obstacles encountered
26 return obstacles;
27 }
28
29 // If we have already visited this cell, skip it
30 if (visited[currentRow][currentCol]) {
31 continue;
32 }
33
34 // Mark the current cell as visited
35 visited[currentRow][currentCol] = true;
36
37 // Explore the neighboring cells
38 for (int h = 0; h < 4; ++h) {
39 int nextRow = currentRow + directions[h];
40 int nextCol = currentCol + directions[h + 1];
41
42 // Check the boundaries of the grid
43 if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols) {
44 // If the next cell is free (no obstacle)
45 if (grid[nextRow][nextCol] == 0) {
46 // Add it to the front of the queue to be processed with the same obstacle count
47 queue.offerFirst(new int[] {nextRow, nextCol, obstacles});
48 } else {
49 // If there's an obstacle, add it to the end of the queue with the obstacle count incremented by 1
50 queue.offerLast(new int[] {nextRow, nextCol, obstacles + 1});
51 }
52 }
53 }
54 }
55 // We include a return statement to satisfy the compiler, although the true return occurs inside the loop
56 return -1; // This will never be reached as the problem guarantees a path exists
57 }
58}
59
1#include <vector>
2#include <deque>
3#include <tuple>
4#include <cstring>
5
6class Solution {
7public:
8 // This function computes the minimum number of obstacles that need to be removed
9 // to move from the top-left corner to the bottom-right corner of the grid.
10 int minimumObstacles(std::vector<std::vector<int>>& grid) {
11 int rows = grid.size(); // The number of rows in the grid
12 int cols = grid[0].size(); // The number of columns in the grid
13
14 // deque to perform BFS with a slight modification to handle 0-cost and 1-cost paths
15 std::deque<std::tuple<int, int, int>> queue;
16 queue.emplace_back(0, 0, 0); // Start from the top-left corner (0,0)
17
18 // Visited array to keep track of visited cells
19 bool visited[rows][cols];
20 std::memset(visited, 0, sizeof(visited));
21
22 // Direction vectors for up, right, down and left movements
23 int directions[5] = {-1, 0, 1, 0, -1};
24
25 while (!queue.empty()) {
26 // Get the current cell's row, column, and obstacle count
27 auto [currentRow, currentCol, obstacleCount] = queue.front();
28 queue.pop_front();
29
30 // If we have reached the bottom-right corner, return the obstacle count
31 if (currentRow == rows - 1 && currentCol == cols - 1) {
32 return obstacleCount;
33 }
34
35 // Skip this cell if it's already been visited
36 if (visited[currentRow][currentCol]) {
37 continue;
38 }
39
40 // Mark the current cell as visited
41 visited[currentRow][currentCol] = true;
42
43 // Loop through the possible movements using the direction vectors
44 for (int dir = 0; dir < 4; ++dir) {
45 int newRow = currentRow + directions[dir];
46 int newCol = currentCol + directions[dir + 1];
47
48 // Check if the new position is valid and within the grid boundaries
49 if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
50 // If new cell has no obstacles, it has the same obstacle count 'k'
51 // and it is pushed to the front to give it higher priority
52 if (grid[newRow][newCol] == 0) {
53 queue.emplace_front(newRow, newCol, obstacleCount);
54 }
55 // If new cell has an obstacle, increase the obstacle count 'k' by 1
56 // and it is pushed to the back
57 else {
58 queue.emplace_back(newRow, newCol, obstacleCount + 1);
59 }
60 }
61 }
62 }
63
64 // If the function somehow reaches here (it should not), return -1 as an error signal.
65 // This return statement is logically unreachable because the loop is guaranteed to break
66 // when the bottom-right corner is reached.
67 return -1;
68 }
69};
70
1function minimumObstacles(grid: number[][]): number {
2 const rows = grid.length,
3 columns = grid[0].length; // Define the number of rows and columns of the grid
4 const directions = [ // Directions for traversal: right, left, down, up
5 [0, 1],
6 [0, -1],
7 [1, 0],
8 [-1, 0],
9 ];
10 let obstacleCount = Array.from({ length: rows }, () => new Array(columns).fill(Infinity)); // Initialize obstacle count for each cell with Infinity
11 obstacleCount[0][0] = 0; // Starting point has 0 obstacles
12 let deque = [[0, 0]]; // Double-ended queue to keep track of which cell to visit next
13
14 while (deque.length > 0) {
15 const [currentX, currentY] = deque.shift(); // Extract current cell coordinates
16
17 for (const [dx, dy] of directions) {
18 const [nextX, nextY] = [currentX + dx, currentY + dy]; // Calculate adjacent cell coordinates
19
20 if (nextX < 0 || nextX >= rows || nextY < 0 || nextY >= columns) {
21 continue; // Out of bounds check
22 }
23
24 const currentCost = grid[nextX][nextY]; // Cost of the adjacent cell (0 for open cell, 1 for cell with an obstacle)
25
26 if (obstacleCount[currentX][currentY] + currentCost >= obstacleCount[nextX][nextY]) {
27 continue; // If the new path isn't better, continue to the next adjacent cell
28 }
29
30 obstacleCount[nextX][nextY] = obstacleCount[currentX][currentY] + currentCost; // Update the obstacle count for the cell
31
32 if (currentCost === 0) {
33 deque.unshift([nextX, nextY]); // If no obstacle, add to the front of the queue
34 } else {
35 deque.push([nextX, nextY]); // If there's an obstacle, add to the back of the queue
36 }
37 }
38 }
39
40 return obstacleCount[rows - 1][columns - 1]; // Returns the minimum number of obstacles to reach the bottom-right corner
41}
42
Time and Space Complexity
Time Complexity
The time complexity of the algorithm can be estimated by considering the number of operations it performs. The algorithm uses a queue that can have at most every cell (i, j)
from the grid enqueued, and the grid has m * n
cells. Each cell is inserted into the queue at most once, since we're using a set of visited nodes to prevent re-visitation.
The deque
operations appendleft
and popleft
have O(1)
time complexity. The for loop executes at most four times for each cell, corresponding to the four possible directions one can move in the grid.
Considering all of this, the overall time complexity is O(m * n)
, as every cell is considered at most once.
Space Complexity
The space complexity consists of the space needed for the queue and the set of visited cells.
The queue can store up to m * n
elements, if all cells are inserted, and the set will at the same time contain a maximum of m * n
elements as well to track visited cells. The sum is 2 * m * n
but in terms of Big O notation, the constants are ignored.
Thus, the space complexity is O(m * n)
for the queue and the visited set combined.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these properties could exist for a graph but not a tree?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Shortest Path Between A and B Prereq BFS on Graph problems graph_bfs Given an unweighted connected graph return the length of the shortest path between two nodes A and B in terms of the number of edges Assume there always exists a path between nodes A and B Input graph
Want a Structured Path to Master System Design Too? Don’t Miss This!