Mastering Minimum Obstacle Removal in JavaScript

The provided code implements a solution to the Minimum Obstacle Removal to Reach Corner problem in JavaScript using Dijkstra’s algorithm. The goal is to traverse a binary grid (where 0 represents a passable cell and 1 represents an obstacle) from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1) while removing the minimum number of obstacles.

The solution begins by initializing the grid’s dimensions (m and n), and defining directional vectors for moving up, down, left, and right. A result matrix is created, filled with Infinity, to store the minimum obstacles removed to reach each cell, starting with result[0][0] = 0. A priority queue (MinPriorityQueue) is used to prioritize cells based on the number of obstacles removed.

The main loop processes cells from the queue. For each cell, its neighbors are evaluated to ensure they are within bounds. If a neighbor cell has a better path (fewer obstacles removed), its value in the result matrix is updated, and it is added to the priority queue for further exploration.

Finally, the function returns the value at the bottom-right corner (result[m-1][n-1]), representing the minimum obstacles removed to reach the destination. The code efficiently combines a priority queue and grid traversal to solve this pathfinding problem.

My Code:

codevar minimumObstacles = function(grid) {
    let m = grid.length;
    let n = grid[0].length;
    let directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

    let result = Array.from({ length: m }, () => new Array(n).fill(Infinity));
    result[0][0] = 0;

    let priorityQueue = new MinPriorityQueue({ priority: x => x.weight });
    priorityQueue.enqueue({ weight: 0, position: [0, 0] });

    while (!priorityQueue.isEmpty()) {
        let { element } = priorityQueue.dequeue();
        let { weight: obstaclesRemoved, position } = element;
        let [i, j] = position;

        for (let direction of directions) {
            let x = i + direction[0];
            let y = j + direction[1];

            if (x < 0 || x >= m || y < 0 || y >= n) {
                continue;
            }

            let additionalObstacle = grid[x][y] === 1 ? 1 : 0;

            if (obstaclesRemoved + additionalObstacle < result[x][y]) {
                result[x][y] = obstaclesRemoved + additionalObstacle;
                priorityQueue.enqueue({
                    weight: obstaclesRemoved + additionalObstacle,
                    position: [x, y]
                });
            }
        }
    }

    return result[m - 1][n - 1];
};

Mastering Minimum Obstacle Removal in JavaScript

Pathfinding problems are a cornerstone of algorithmic challenges, and LeetCode’s Minimum Obstacle Removal to Reach Corner is an excellent example. This problem leverages Dijkstra’s algorithm to minimize obstacles encountered while traversing a grid. In this blog, we’ll break down the solution step-by-step in JavaScript.

Problem Description

Given a binary m x n grid, the goal is to move from the top-left corner (0,0) to the bottom-right corner (m-1, n-1) with the minimum obstacles removed. Obstacles are represented by 1s, while passable cells are 0s.

Key Concepts

• Dijkstra’s Algorithm: This greedy algorithm finds the shortest path in a weighted graph. Here, “weights” correspond to the number of obstacles removed.
• Priority Queue: To prioritize cells based on the number of obstacles removed.
• Grid Traversal: Using directional vectors to explore neighbors.

JavaScript Solution

Step-by-Step Breakdown

1. Initialization:
   • Retrieve the grid’s dimensions (m and n).
   • Define directional vectors for movement: up, down, left, right.
   • Initialize a result matrix with Infinity values, where result[i][j] represents the minimum obstacles removed to reach (i, j). Start with result[0][0] = 0.
2. Priority Queue:
   • Use a MinPriorityQueue to process grid cells by the number of obstacles removed. This ensures cells with fewer obstacles are explored first.
3. Grid Traversal:
   • Use a loop to dequeue the top-priority cell.
   • For each cell, explore its neighbors using the directional vectors.
   • If a neighbor is within bounds, calculate the new number of obstacles removed (additionalObstacle). Update the result matrix and enqueue the neighbor if this path is better.
4. Result:
   • After the queue is empty, return the value at the bottom-right corner (result[m-1][n-1]).

Complete Code

codevar minimumObstacles = function(grid) {
    let m = grid.length;
    let n = grid[0].length;
    let directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

    let result = Array.from({ length: m }, () => new Array(n).fill(Infinity));
    result[0][0] = 0;

    let priorityQueue = new MinPriorityQueue({ priority: x => x.weight });
    priorityQueue.enqueue({ weight: 0, position: [0, 0] });

    while (!priorityQueue.isEmpty()) {
        let { element } = priorityQueue.dequeue();
        let { weight: obstaclesRemoved, position } = element;
        let [i, j] = position;

        for (let direction of directions) {
            let x = i + direction[0];
            let y = j + direction[1];

            if (x < 0 || x >= m || y < 0 || y >= n) {
                continue;
            }

            let additionalObstacle = grid[x][y] === 1 ? 1 : 0;

            if (obstaclesRemoved + additionalObstacle < result[x][y]) {
                result[x][y] = obstaclesRemoved + additionalObstacle;
                priorityQueue.enqueue({
                    weight: obstaclesRemoved + additionalObstacle,
                    position: [x, y]
                });
            }
        }
    }

    return result[m - 1][n - 1];
};

Explanation with an Example

Input:

codegrid = [
    [0, 1, 1],
    [1, 1, 0],
    [1, 0, 0]
];

Output:

code2

Walkthrough:

• Start at (0,0) with 0 obstacles removed.
• Move to adjacent cells, calculating the number of obstacles.
• Use the priority queue to always prioritize cells with fewer obstacles.
• Ultimately, reach (2,2) with 2 obstacles removed.

Complexity Analysis

1. Time Complexity:
   • Each cell is processed at most once, leading to O(m * n) operations.
   • For each cell, the neighbors are checked in constant time.
2. Space Complexity:
   • The result matrix and priority queue require O(m * n) space.

Key Takeaways

• Combining Dijkstra’s algorithm with a priority queue provides an efficient approach to solving this problem.
• Understanding graph algorithms and their applications to grid problems is crucial for competitive programming.