Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2290.html

2290. Minimum Obstacle Removal to Reach Corner

• Difficulty: Hard.
• Related Topics: Array, Breadth-First Search, Graph, Heap (Priority Queue), Matrix, Shortest Path.
• Similar Questions: Shortest Path in a Grid with Obstacles Elimination.

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

• Java
• C++
• Python

• class Solution {
      public int minimumObstacles(int[][] grid) {
          int n = grid.length;
          int m = grid[0].length;
          int[][] dirs = new int[][] { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
          Queue<State> q = new PriorityQueue<>((a, b) -> a.removed - b.removed);
          q.add(new State(0, 0, 0));
          boolean[][] visited = new boolean[n][m];
          visited[0][0] = true;
          while (!q.isEmpty()) {
              State state = q.poll();
              if (state.r == n - 1 && state.c == m - 1) {
                  return state.removed;
              }
              for (int[] d : dirs) {
                  int nr = state.r + d[0];
                  int nc = state.c + d[1];
                  if (nr < 0 || nc < 0 || nr == n || nc == m || visited[nr][nc]) {
                      continue;
                  }
                  visited[nr][nc] = true;
                  State next = new State(nr, nc, state.removed);
                  if (grid[nr][nc] == 1) {
                      next.removed++;
                  }
                  q.add(next);
              }
          }
          return -1;
      }
  
      private static class State {
          int r;
          int c;
          int removed;
  
          State(int r, int c, int removed) {
              this.r = r;
              this.c = c;
              this.removed = removed;
          }
      }
  }
  

• Todo
  

• class Solution:
      def minimumObstacles(self, grid: List[List[int]]) -> int:
          m, n = len(grid), len(grid[0])
          q = deque([(0, 0, 0)])
          vis = set()
          dirs = (-1, 0, 1, 0, -1)
          while 1:
              i, j, k = q.popleft()
              if i == m - 1 and j == n - 1:
                  return k
              if (i, j) in vis:
                  continue
              vis.add((i, j))
              for a, b in pairwise(dirs):
                  x, y = i + a, j + b
                  if 0 <= x < m and 0 <= y < n:
                      if grid[x][y] == 0:
                          q.appendleft((x, y, k))
                      else:
                          q.append((x, y, k + 1))
  
  ############
  
  # 2290. Minimum Obstacle Removal to Reach Corner
  # https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner
  
  class Solution:
      def minimumObstacles(self, grid: List[List[int]]) -> int:
          rows, cols = len(grid), len(grid[0])
  ​
          dist = [[float('inf')] * cols for _ in range(rows)]
          dist[0][0] = 0
          
          heap = [(0, 0, 0)]
          
          while heap:
              k, x, y = heappop(heap)
              
              if dist[x][y] != k:
                  continue
              
              for dx, dy in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                  if 0 <= dx < rows and 0 <= dy < cols:
                      old = dist[dx][dy]
                      new = k + grid[dx][dy]
                      
                      if new < old:
                          dist[dx][dy] = new
                          heappush(heap, (new, dx, dy))
                          
          return dist[-1][-1]
  
  

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).

All Problems

All Solutions