How do you approach Shortest Path in Grid with Obstacles?

Use BFS where each state includes the position AND the number of remaining obstacle eliminations.

What is the time complexity of Shortest Path in Grid with Obstacles?

Time complexity: O(m n k). Space complexity: O(m n k).

What are common mistakes on Shortest Path in Grid with Obstacles?

Building the adjacency list in one direction on an undirected graph. Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest. Ignoring self-loops and parallel edges when the constraints allow them.

gitGood.dev

← Back to problems

Shortest Path in Grid with Obstacles

HardAlgorithms

Description

You are given an `m x n` integer matrix `grid` where each cell is either `0` (empty) or `1` (obstacle). You can move up, down, left, or right from and to an empty cell in one step. Return the minimum number of steps to walk from the upper left corner `(0, 0)` to the lower right corner `(m - 1, n - 1)` given that you can eliminate **at most** `k` obstacles. If it is not possible to find such a walk, return `-1`.

Example 1

Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1

Output: 6

Explanation: The shortest path without eliminating any obstacle is 10. With one elimination, we can remove the obstacle at (1,1) to get a path of length 6.

Example 2

Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1

Output: -1

Explanation: We need to eliminate at least two obstacles to find a path.

Constraints

- m == grid.length - n == grid[i].length - 1 <= m, n <= 40 - 0 <= k <= m * n - grid[i][j] is either 0 or 1. - grid[0][0] == 0 and grid[m-1][n-1] == 0

Shortest Path in Grid with Obstacles: approach, complexity and pitfalls

A hard graphs problem, graded against 6 test cases (3 of them hidden).

The pattern: Graphs

Nodes and edges - traversal, connectivity, cycles, and shortest paths.

Reach for it when you see: Explicit edges, a grid treated as a graph, or dependencies between items.

More Graphsproblems →

If you are stuck

Show the 3-step hint ladder

Use BFS where each state includes the position AND the number of remaining obstacle eliminations.
The state is (row, col, remaining_k). Two states are different if any component differs.
Use a 3D visited array: visited[row][col][remaining_k].

The optimal approach

Show the approach: BFS with State (row, col, remaining_k)

Standard BFS but the state includes how many obstacle eliminations remain. When moving to a cell with an obstacle, decrement k. A cell can be visited multiple times with different remaining k values. Use a 3D visited array to avoid revisiting the same state.

Time: O(m * n * k)
Space: O(m * n * k)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Graphs mistakes

These apply to the pattern as a whole, not just this problem.

Building the adjacency list in one direction on an undirected graph.
Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest.
Ignoring self-loops and parallel edges when the constraints allow them.