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 (1s) 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

  1. Initialize the deque q with a tuple containing the starting position and the initial number of obstacles removed (0, 0, 0).
  2. Create a vis set to record visited positions and avoid revisiting them.
  3. The dirs tuple is used to calculate the adjacent cells' positions with the help of a helper function like pairwise.
  4. Enter a loop that continues until the end condition is met (reaching (m - 1, n - 1)).
  5. Use popleft to get the current position and the count k of the obstacles removed.
  6. If the target position is reached, return k.
  7. If the position has been visited before ((i, j) in vis), just continue to the next iteration.
  8. Otherwise, mark the position as visited by adding (i, j) to vis.
  9. Iterate over all possible directions, and calculate the adjacent cell positions (x, y).
  10. 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 obstacles k.
  11. If (x, y) has an obstacle, append it to the end of the deque and increment the count of removed obstacles by 1.

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 Evaluator

Example 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:

  1. We start by initializing the deque q with the starting position and the initial number of obstacles removed, which is 0. So q = deque([(0, 0, 0)]).

  2. The vis set is initialized to ensure we don't visit the same positions repeatedly. In the beginning, it's empty: vis = set().

  3. The BFS begins. We dequeue the first element (i, j, k) = (0, 0, 0), where (i, j) represents the current cell, and k is the number of removed obstacles so far.

  4. 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 of q: q = deque([(0, 1, 1)]).
    • Down (1, 0): No obstacle. We add it to the front of q: q = deque([(1, 0, 0), (0, 1, 1)]).
  5. We mark the current cell (0, 0) as visited: vis.add((0, 0)).

  6. Now the deque q has cells to process, so we take the one from the front, which is (1, 0, 0).

  7. 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)]).
  8. We mark the cell (1, 0) as visited: vis.add((1, 0)).

  9. The steps repeat, dequeuing from the front, checking adjacent cells, and enqueueing in the deque according to the rules.

  10. 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)]).

  11. Again, we mark (2, 0) as visited: vis.add((2, 0)).

  12. Dequeuing (2, 1, 0), we can go right to the target (2, 2) with no obstacle. We add it to the front.

  13. Mark (2, 1) as visited and check the next cell from q.

  14. Finally, we reach (2, 2) which is the target. We have not needed to remove any obstacles, so we return k = 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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of these properties could exist for a graph but not a tree?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!


Load More