Minimum Obstacle Removal to Reach Corner LeetCode Solution

Problem – Minimum Obstacle Removal to Reach Corner LeetCode solution

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

Minimum Obstacle Removal to Reach Corner LeetCode Solution in Java

public int minimumObstacles(int[][] grid) {
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        int[][] dir = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int m = grid.length, n = grid[0].length;
        int[][] count = new int[m][n];
        for(int i = 0;i < m;i++) {
            Arrays.fill(count[i], Integer.MAX_VALUE);
        }
        count[0][0] = 0;
        q.offer(new int[]{0, 0, 0});
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0];
            int y = cur[1];
            int cost = cur[2];
            if(x == m - 1 && y == n - 1) {
                return cost;
            }
            for(int i = 0;i < 4;i++) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];
                if(nx < 0 || ny < 0 || nx >= m || ny >= n) {
                    continue;
                }
                int now = cur[2];
                if(grid[nx][ny] == 1) {
                    now++;
                }
                if(now >= count[nx][ny]) {
                    continue;
                }
                
                count[nx][ny] = now;
                q.offer(new int[] {nx, ny, now});
            }
        }
        return -1;
    }

Minimum Obstacle Removal to Reach Corner LeetCode Solution in C++

class Solution {
public:
    int minimumObstacles(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> dp(n, vector<int>(m, 1e5 + 1));
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
        
        pq.push({grid[0][0], 0, 0});
        int dirs[4][2] = {{0, 1},{-1, 0},{1, 0},{0, -1}};
        while (!pq.empty()) {
            auto [c, i, j] = pq.top();
            pq.pop();
            
            if (i == n - 1 && j == m - 1) {
                return c;
            }
            
            for (auto &d: dirs) {
                int x = d[0] + i;
                int y = d[1] + j;
                
                if (x < 0 || y < 0 || x >= n || y >= m)
                    continue;
                
                if (dp[x][y] > grid[x][y] + c) {
                    dp[x][y] = grid[x][y] + c;
                    pq.push({grid[x][y] + c, x, y});
                }
            }
        }
        
        return -1;
    }
};

Minimum Obstacle Removal to Reach Corner LeetCode Solution in Python

class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        q = [(0, 0, 0)]
        dist = [[float('inf') for _ in range(n)] for _ in range(m)]

        while q:
            size = len(q)
            for _ in range(size):
                obs, x, y = heapq.heappop(q)
                if dist[x][y] < float('inf'): continue
                obs += grid[x][y]
                dist[x][y] = obs
                if x + 1 < m: heapq.heappush(q, (obs, x + 1, y))
                if x > 0: heapq.heappush(q, (obs, x - 1, y))
                if y + 1 < n: heapq.heappush(q, (obs, x, y + 1))
                if y > 0: heapq.heappush(q, (obs, x, y - 1))
        return dist[m - 1][n - 1]

Minimum Obstacle Removal to Reach Corner LeetCode Solution Review:

In our experience, we suggest you solve this Minimum Obstacle Removal to Reach Corner LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Minimum Obstacle Removal to Reach Corner LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Minimum Obstacle Removal to Reach Corner LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions