The “Shortest Path in a Grid with Obstacles Elimination” problem asks you to find the minimum number of steps needed to move from the top-left corner of a grid to the bottom-right corner. You can move up, down, left, or right, and the grid contains empty cells and obstacles. The twist is that you are allowed to eliminate up to k obstacles along your path, turning those blocked cells into passable steps. If no valid path exists even after using eliminations, the result should indicate failure.
This problem is compelling because it looks like a standard shortest path task, but the obstacle elimination budget changes everything. The shortest geometric route might cut through obstacles, and whether that route is valid depends on how many eliminations you can afford. As a result, you are not just searching for a path; you are searching for a path under resource constraints.
Why traditional grid shortest path isn’t enough
In a basic grid shortest path problem with uniform move costs, breadth-first search works perfectly because it guarantees that the first time you reach the destination, you did so in the minimum number of steps. However, obstacle elimination introduces an extra dimension: arriving at the same cell with different remaining eliminations is not the same state.
If you ignore this, you risk discarding paths that are longer early but preserve eliminations for later, which can lead to a shorter overall solution. The problem forces you to treat “position plus remaining eliminations” as the true state, not just position alone.
Check out Sum of Left Leaves and Bitwise AND of Numbers Range coding problem solutions.
Recognizing the expanded state space
The key insight is that the grid alone does not define your progress. Your elimination budget is part of your progress as well. Two visits to the same cell can have very different future potential depending on how many obstacles you have already removed.
This means the problem becomes a shortest path search in an expanded graph. Each node in this conceptual graph represents a triple: row, column, and remaining eliminations. Edges represent moving to an adjacent cell, consuming one elimination if that cell is an obstacle.
Why breadth-first search still works
Even with the expanded state, breadth-first search remains the right tool because each move still has the same cost: one step. The only difference is that you are running BFS over a larger set of states.
The BFS queue explores states in increasing step count. The first time you reach the destination cell in any valid state, you have found the shortest path length, because BFS guarantees minimal steps in an unweighted graph.
Managing visited states correctly
The most important implementation detail is how you track visited states. In a normal grid BFS, you mark a cell as visited once. Here, that is not enough. You must consider whether you have visited a cell with an equal or better elimination budget.
A clean way to think about this is dominance. If you reach a cell with more remaining eliminations than before, that new state is strictly better because it gives you more flexibility going forward. If you reach a cell with fewer or equal remaining eliminations compared to an already-seen state, that new state is not worth exploring because it cannot lead to a better outcome.
This dominance concept prevents the BFS from exploding while still preserving correctness.
How obstacle elimination affects transitions
When you move into a neighboring cell, you check whether it is an obstacle. If it is not, you transition without changing your remaining elimination budget. If it is an obstacle, you can only transition if you still have eliminations left, and the remaining budget decreases by one.
This simple rule is what ties together the spatial search and the resource constraint. Every step updates not only your location but also your remaining capacity to break through future obstacles.
Why this approach guarantees the shortest path
The algorithm guarantees correctness because it explores states in nondecreasing order of steps, and it never discards a state that could lead to a better solution. By tracking the best elimination budget seen at each cell, it ensures that only dominated states are pruned.
When the destination is reached, the step count associated with that BFS layer is the smallest possible, because any alternative path would have required at least as many moves to reach a destination state.
Time and space complexity considerations
The complexity depends on the grid size and the value of k. In the worst case, each cell can be visited multiple times with different remaining elimination budgets. However, dominance pruning greatly reduces redundant exploration in practice, because you typically only keep the best budgets per cell.
Space usage is driven by the BFS queue and the visited tracking structure. This overhead is expected, as the problem is essentially shortest path search over a larger state graph.
Why this problem is popular in interviews
This problem shows up often in interviews because it tests whether candidates can adapt a familiar algorithm to a more complex state representation. Many people know BFS for grid shortest paths, but fewer recognize when “visited” must include additional dimensions like resource budgets.
It also tests whether you can reason about pruning safely. The dominance idea is subtle, but it is exactly what makes the solution both correct and efficient.
What this problem teaches beyond grids
Beyond grid traversal, this problem teaches a powerful lesson about shortest path problems with constraints. Whenever movement depends on limited resources such as fuel, coupons, or obstacle removals, the state must include both position and remaining resource.
If you can clearly explain why position alone is not enough, how BFS works on the expanded state space, and why dominance-based pruning preserves correctness, you demonstrate strong algorithmic maturity. That depth of understanding makes “Shortest Path in a Grid with Obstacles Elimination” an excellent exercise in constrained shortest-path modeling.
If you want more coding problems explained, check out:
Top comments (0)