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

  • 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