D
DevExCode

LeetCode 2290: Minimum Obstacle Removal to Reach Corner Solution

Master LeetCode problem 2290 (Minimum Obstacle Removal to Reach Corner), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2290. Minimum Obstacle Removal to Reach Corner

Hard
ArrayBreadth-First SearchGraphHeap (Priority Queue)MatrixShortest Path

Problem Explanation

Explanation

To solve this problem, we can use a breadth-first search (BFS) algorithm. We start from the top-left corner of the grid and explore all possible paths by moving in all four directions (up, down, left, right) from each cell. We keep track of the obstacles removed so far and update the minimum number of obstacles required to reach the bottom-right corner.

We can use a priority queue to explore cells with fewer obstacles first, ensuring we find the path with the minimum obstacles to remove.

Algorithm:

  1. Initialize a priority queue to store cells based on the number of obstacles removed.
  2. Add the top-left corner cell (0, 0) to the priority queue with 0 obstacles removed.
  3. While the priority queue is not empty:
    • Pop the cell with the least obstacles removed.
    • If the cell is the bottom-right corner (m-1, n-1), return the number of obstacles removed.
    • Explore all four directions from the current cell:
      • If the neighbor cell is within the grid bounds and not an obstacle:
        • If the neighbor cell has fewer obstacles removed in the past, add it to the priority queue with updated obstacles count.
  4. If no path is found, return -1.

Time Complexity:

The time complexity of this algorithm is O(m * n * log(m * n)), where m and n are the dimensions of the grid.

Space Complexity:

The space complexity is O(m * n) for the priority queue and visited array.

Solution Code

import java.util.*;

class Solution {
    public int minObstaclesToRemove(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        boolean[][] visited = new boolean[m][n];
        
        pq.offer(new int[]{0, 0, 0});
        
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int row = curr[0];
            int col = curr[1];
            int obstacles = curr[2];
            
            visited[row][col] = true;
            
            if (row == m - 1 && col == n - 1) {
                return obstacles;
            }
            
            for (int[] dir : dirs) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];
                
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol]) {
                    int newObstacles = obstacles + grid[newRow][newCol];
                    pq.offer(new int[]{newRow, newCol, newObstacles});
                }
            }
        }
        
        return -1;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 2290 (Minimum Obstacle Removal to Reach Corner)?

This page provides optimized solutions for LeetCode problem 2290 (Minimum Obstacle Removal to Reach Corner) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2290 (Minimum Obstacle Removal to Reach Corner)?

The time complexity for LeetCode 2290 (Minimum Obstacle Removal to Reach Corner) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2290 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2290 in Java, C++, or Python.

Back to LeetCode Solutions