D
DevExCode

LeetCode 1293: Shortest Path in a Grid with Obstacles Elimination Solution

Master LeetCode problem 1293 (Shortest Path in a Grid with Obstacles Elimination), 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.

1293. Shortest Path in a Grid with Obstacles Elimination

Hard
ArrayBreadth-First SearchMatrix

Problem Explanation

Explanation

To solve this problem, we can use a variation of Dijkstra's algorithm. We will maintain a priority queue to explore the grid cells in a breadth-first search manner while keeping track of the number of obstacles eliminated so far. We will store the current position, the number of steps taken, and the number of obstacles eliminated in the priority queue. We will continue exploring cells until we reach the destination or exhaust all possibilities.

Algorithm:

  1. Create a priority queue to store the current position, steps taken, and obstacles eliminated.
  2. Add the starting cell (0, 0) to the priority queue with steps = 0 and obstacles eliminated = 0.
  3. Initialize a 2D array visited to keep track of the minimum obstacles eliminated at each cell.
  4. Initialize directions for movement: up, down, left, right.
  5. While the priority queue is not empty:
    • Pop the cell with the smallest number of steps from the priority queue.
    • If the current cell is the destination, return the number of steps taken.
    • Iterate through all possible directions and check if the new position is within bounds and not an obstacle.
    • If the new position is valid and can be reached with fewer obstacles eliminated, add it to the priority queue.
  6. If no path is found, return -1.

Time Complexity:

The time complexity of this algorithm is O(mnklog(mn)) where m and n are the dimensions of the grid and k is the maximum number of obstacles that can be eliminated.

Space Complexity:

The space complexity of this algorithm is O(mnk) for the priority queue and the visited array.

Solution Code

class Solution {
    public int shortestPath(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2]));
        pq.offer(new int[]{0, 0, 0});
        int[][] visited = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int r = curr[0], c = curr[1], o = curr[2];
            if (r == m - 1 && c == n - 1) return visited[r][c];
            for (int[] dir : dirs) {
                int newRow = r + dir[0], newCol = c + dir[1];
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
                    int newObstacles = o + grid[newRow][newCol];
                    if (newObstacles <= k && newObstacles < visited[newRow][newCol]) {
                        visited[newRow][newCol] = newObstacles;
                        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 1293 (Shortest Path in a Grid with Obstacles Elimination)?

This page provides optimized solutions for LeetCode problem 1293 (Shortest Path in a Grid with Obstacles Elimination) 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 1293 (Shortest Path in a Grid with Obstacles Elimination)?

The time complexity for LeetCode 1293 (Shortest Path in a Grid with Obstacles Elimination) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1293 on DevExCode?

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

Back to LeetCode Solutions