Naive Pseudo-code

text
function dfs(row, col, current_obstacles):
    if (row, col) is destination:
        min_obstacles = min(min_obstacles, current_obstacles)
        return

    mark (row, col) as visited
    
    for each neighbor:
        cost = grid[neighbor_row][neighbor_col]
        dfs(neighbor_row, neighbor_col, current_obstacles + cost)
        
    unmark (row, col) // backtrack

Analysis of Failure

This approach fails due to Time Limit Exceeded (TLE).

• Time Complexity: In the worst case (an empty grid), the number of simple paths from top-left to bottom-right is exponential, roughly $O(3^{m \times n})$. With constraints where $m \times n$ can reach $10^5$, an exponential solution is computationally impossible.
• Why it fails: DFS blindly explores all paths, including extremely inefficient ones (e.g., spiraling through the entire grid), and recalculates paths to the same cell multiple times without leveraging the optimal substructure of the problem.

Core Insight for Minimum Obstacle Removal to Reach Corner

The key intuition is to treat the grid as a graph where each cell is a node and adjacent cells are connected by directed edges. The weight of an edge directed into a cell depends on the value of that cell:

• Moving into a cell with 0 has a weight of 0.
• Moving into a cell with 1 has a weight of 1.

Standard Breadth-First Search (BFS) only finds the shortest path in an unweighted graph (or where all weights are equal). Because our weights differ ($0$ vs $1$), standard BFS is insufficient as it assumes the first time you reach a node, it is via the shortest path. This assumption holds for hop-count distance but not for weighted distance.

Dijkstra's Algorithm addresses this by using a Priority Queue (Min-Heap) to explore paths. The invariant enforced by Dijkstra is that we always expand the node with the current lowest cumulative cost. This ensures that when we first extract the destination node from the priority queue, we have guaranteed the minimum number of obstacles removed.

Visual Description: Imagine a contour map. The algorithm starts at (0,0) with a "height" (cost) of 0. It expands like water flowing downhill. It floods all reachable 0-cost cells instantly. When it hits a 1-cost cell (a "wall"), the flow pauses until all lower "height" areas are filled. The Priority Queue manages this flow, ensuring we process all possible paths costing $k$ obstacles before considering any path costing $k+1$ obstacles.

Algorithm Strategy: Graph - Shortest Path (Dijkstra's Algorithm)

We will implement Dijkstra's algorithm strictly following the pattern:

1. State Representation: We maintain a 2D array min_obstacles (or dist) of size $m \times n$, initialized to infinity (INT_MAX). min_obstacles[i][j] stores the minimum obstacles removed to reach cell (i, j).
2. Priority Queue: Use a Min-Heap to store tuples (cost, row, col). The heap orders elements primarily by cost in ascending order.
3. Initialization:
   • Set min_obstacles[0][0] = 0.
   • Push (0, 0, 0) onto the heap.
4. Exploration:
   • While the heap is not empty, pop the element with the lowest cost: (current_cost, r, c).
   • If current_cost is greater than min_obstacles[r][c], this is an outdated path; skip it.
   • For each valid neighbor (nr, nc):
     • Calculate new_cost = current_cost + grid[nr][nc].
     • If new_cost < min_obstacles[nr][nc]:
       • Update min_obstacles[nr][nc] = new_cost.
       • Push (new_cost, nr, nc) to the heap.
5. Termination: The moment we pop the destination cell (m-1, n-1) from the heap, its cost is the answer. Alternatively, return min_obstacles[m-1][n-1] after the heap is empty.

Execution Flow

Let's trace the logic for a small example.

1. Start: PQ contains [(0, 0, 0)]. Distance matrix is all $\infty$ except dist[0][0]=0.
2. Pop (0,0,0): Neighbors are (0,1) and (1,0).
   • Suppose grid[0][1] is 1 (obstacle). Cost becomes $0+1=1$. Push (1, 0, 1). Update dist[0][1]=1.
   • Suppose grid[1][0] is 0 (empty). Cost becomes $0+0=0$. Push (0, 1, 0). Update dist[1][0]=0.
3. Next Iteration: PQ contains [(0, 1, 0), (1, 0, 1)].
   • The algorithm pops (0, 1, 0) because it has the lower cost (Greedy choice).
   • We process neighbors of (1, 0).
4. Continuing: The algorithm prioritizes exploring "free" paths (cost 0) before "expensive" paths (cost 1).
5. Target Reached: Eventually, the coordinates (m-1, n-1) are popped from the PQ. The associated cost is returned immediately.

Proof of Correctness

Dijkstra's algorithm is proven to find the shortest path in a graph with non-negative edge weights.

• Invariant: At any step, for every visited node $v$, the distance recorded is the shortest possible distance from the source.
• Relaxation: When we relax an edge $(u, v)$, we update the distance to $v$ only if a shorter path is found.
• Greedy Choice: By always selecting the node with the smallest tentative distance from the Priority Queue, we guarantee that we never process a node until we have found the absolute shortest path to it (assuming non-negative weights).
• Since grid values are only 0 or 1, weights are non-negative, satisfying the requirement for Dijkstra's correctness.

Reference Implementation

C++ Solution for LeetCode 2290

cpp
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

class Solution {
public:
    int minimumObstacles(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        // Min-heap storing {obstacles, row, col}
        // Orders by obstacles ascending
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
        
        // Distance matrix to track minimum obstacles to each cell
        vector<vector<int>> dist(m, vector<int>(n, 1e9));
        
        // Directions array for moving up, down, left, right
        int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        // Start at (0, 0) with 0 cost
        dist[0][0] = 0;
        pq.push({0, 0, 0});
        
        while (!pq.empty()) {
            auto [cost, r, c] = pq.top();
            pq.pop();
            
            // If we reached the target, return the cost
            if (r == m - 1 && c == n - 1) {
                return cost;
            }
            
            // Optimization: If current path is worse than already found, skip
            if (cost > dist[r][c]) {
                continue;
            }
            
            // Explore neighbors
            for (auto& dir : dirs) {
                int nr = r + dir[0];
                int nc = c + dir[1];
                
                // Check bounds
                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    int newCost = cost + grid[nr][nc];
                    
                    // If a cheaper path is found, update and push to PQ
                    if (newCost < dist[nr][nc]) {
                        dist[nr][nc] = newCost;
                        pq.push({newCost, nr, nc});
                    }
                }
            }
        }
        
        return -1; // Should not reach here
    }
};

Java Solution for LeetCode 2290

java
import java.util.PriorityQueue;
import java.util.Arrays;

class Solution {
    public int minimumObstacles(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        // Priority Queue stores int[] {cost, row, col}
        // Ordered by cost ascending
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        
        // Distance matrix
        int[][] dist = new int[m][n];
        for (int[] row : dist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        // Start at (0, 0)
        dist[0][0] = 0;
        pq.offer(new int[]{0, 0, 0});
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int cost = current[0];
            int r = current[1];
            int c = current[2];
            
            if (r == m - 1 && c == n - 1) {
                return cost;
            }
            
            // Optimization: Skip stale entries
            if (cost > dist[r][c]) {
                continue;
            }
            
            for (int[] dir : dirs) {
                int nr = r + dir[0];
                int nc = c + dir[1];
                
                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    int newCost = cost + grid[nr][nc];
                    
                    if (newCost < dist[nr][nc]) {
                        dist[nr][nc] = newCost;
                        pq.offer(new int[]{newCost, nr, nc});
                    }
                }
            }
        }
        
        return -1;
    }
}

Python Solution for LeetCode 2290

python
import heapq

class Solution:
    def minimumObstacles(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # Priority Queue stores (cost, row, col)
        pq = [(0, 0, 0)]
        
        # Distance matrix initialized to infinity
        dist = [[float('inf')] * n for _ in range(m)]
        dist[0][0] = 0
        
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        while pq:
            cost, r, c = heapq.heappop(pq)
            
            if r == m - 1 and c == n - 1:
                return cost
            
            # Optimization: Skip if we found a shorter path to this cell already
            if cost > dist[r][c]:
                continue
            
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                
                if 0 <= nr < m and 0 <= nc < n:
                    new_cost = cost + grid[nr][nc]
                    
                    if new_cost < dist[nr][nc]:
                        dist[nr][nc] = new_cost
                        heapq.heappush(pq, (new_cost, nr, nc))
                        
        return -1

Why is my Dijkstra implementation slow?

• Mistake: Forgetting the check if (cost > dist[r][c]) continue; after popping from the heap.
• Why: The heap may contain multiple entries for the same node (Lazy Deletion). We only want to process the one with the minimal cost.
• Consequence: You re-process nodes unnecessarily, degrading performance from $O(E \log V)$ to significantly worse.