Problem

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 _theminimum 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).

Examples

Example 1:

$$ \begin{array}{|c|c|c|} \hline 0 & \times & \times \\ \hline \times & \times & 0 \\ \hline \times & \times & 0 \\ \hline \end{array} \implies \begin{array}{|c|c|c|} \hline \colorbox{green} 0 & \colorbox{green}0 & \colorbox{green} 0 \\ \hline \times & \times & \colorbox{green}{0} \\ \hline \times & \times & \colorbox{green}{0} \\ \hline \end{array} $$

1
2
3
4
5

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:

$$ \begin{array}{|c|c|c|c|c|} \hline 0 & \times & 0 & 0 & 0 \\ \hline 0 & \times & 0 & \times & 0 \\ \hline 0 & 0 & 0 & \times & 0 \\ \hline \end{array} $$

1
2
3

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.length
  • n == grid[i].length
  • 1 <= m, n <= 105
  • 2 <= m * n <= 105
  • grid[i][j] is either 0 or 1.
  • grid[0][0] == grid[m - 1][n - 1] == 0

Solution

Method 1 - Using BFS

Here is the approach:

  1. Problem Understanding:
    • You need to find the minimum number of obstacles (1s) that need to be removed to travel from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1) of a grid.
  2. Graph Search Algorithm:
    • This problem is best approached using a shortest path algorithm in an unweighted grid with obstacles that can be removed.
    • Breadth-First Search (BFS) is appropriate here, especially a variant called 0-1 BFS since there are only two types of cells (0s and 1s).
  3. 0-1 BFS:
    • 0-1 BFS uses a deque (double-ended queue) to achieve the desired efficiency. In this approach, use the front of the deque for cells with value 0 and the back of the deque for cells with value 1.
    • Start from the top-left cell, and for each cell, explore its neighbours. If a neighbour is an empty cell (0), add it to the front of the deque. If it’s an obstacle (1), add it to the back.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    public int minimumObstacles(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        Deque<int[]> dq = new LinkedList<>();
        int[][] dist = new int[m][n];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        dist[0][0] = 0;
        dq.addFirst(new int[]{0, 0});
        
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        while (!dq.isEmpty()) {
            int[] curr = dq.pollFirst();
            int x = curr[0], y = curr[1];
            
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                
                if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
                    int ndist = dist[x][y] + grid[nx][ny];
                    if (ndist < dist[nx][ny]) {
                        dist[nx][ny] = ndist;
                        if (grid[nx][ny] == 0) {
                            dq.addFirst(new int[]{nx, ny});
                        } else {
                            dq.addLast(new int[]{nx, ny});
                        }
                    }
                }
            }
        }
        
        return dist[m-1][n-1];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dq = deque([(0, 0)])
        dist = [[float('inf')] * n for _ in range(m)]
        dist[0][0] = 0
        
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        
        while dq:
            x, y = dq.popleft()
            
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                
                if 0 <= nx < m and 0 <= ny < n:
                    new_dist = dist[x][y] + grid[nx][ny]
                    if new_dist < dist[nx][ny]:
                        dist[nx][ny] = new_dist
                        if grid[nx][ny] == 0:
                            dq.appendleft((nx, ny))
                        else:
                            dq.append((nx, ny))
                            
        return dist[m-1][n-1]

Complexity

  • ⏰ Time complexity: O(m * n), where m is the number of rows and n is the number of columns since each cell is processed at most once.
  • 🧺 Space complexity: O(m * n) due to the space required for the deque and visited tracking.