LeetCode 1293 - Shortest Path in a Grid with Obstacles Elimination

LeetCode Problem 1293

Difficulty: 🔴 Hard
Topics: Array, Breadth-First Search, Matrix

Solution

Problem Understanding

This problem asks us to find the minimum number of steps required to move from the top-left corner of a grid to the bottom-right corner. The grid contains two kinds of cells:

• 0, representing an empty cell that can be entered freely
• 1, representing an obstacle

Normally, obstacles block movement. However, we are allowed to eliminate up to k obstacles during the journey. Eliminating an obstacle means we may move through that blocked cell while consuming one unit from our obstacle elimination budget.

Movement is restricted to the four cardinal directions:

• up
• down
• left
• right

Each move costs exactly one step. The goal is to minimize the total number of steps needed to reach the destination.

The input consists of:

• grid, an m x n matrix
• k, the maximum number of obstacles we may remove

The output is:

• the minimum number of steps required to reach (m - 1, n - 1)
• -1 if no valid path exists

The constraints are important because they guide us toward the appropriate algorithmic strategy.

• m, n <= 40
• therefore, the grid contains at most 1600 cells
• k may be as large as m * n

A brute-force search over all possible paths would explode combinatorially and become infeasible. However, the grid size is small enough that a graph traversal algorithm with carefully managed state can work efficiently.

One subtle but critical detail is that reaching the same cell with different remaining eliminations represents different states. For example:

• arriving at (2,3) with 5 eliminations left is strictly better than arriving there with 1 elimination left
• therefore, position alone is not enough to represent visited states

There are also several edge cases worth noting upfront:

• The grid may already be a single cell, meaning the answer is 0.
• A shortest geometric path may be impossible unless obstacles are removed.
• Multiple paths may reach the same cell with different elimination counts.
• If k is very large, we can effectively ignore many obstacles and take a nearly direct shortest route.

Approaches

Brute Force Approach

A naive solution would attempt to explore every possible path from the start to the destination using Depth-First Search.

At every step, we would:

• move in four directions
• optionally eliminate an obstacle if encountered
• continue recursively until reaching the destination

This approach is correct because it eventually explores every valid path. Among all successful paths, we could track the minimum path length.

However, the number of possible paths grows exponentially. Even on relatively small grids, the search space becomes enormous because:

• paths can revisit cells
• the same cell may be reached with different remaining eliminations
• many branches lead to dead ends

Without aggressive pruning, this approach becomes computationally infeasible.

Optimal Approach, Breadth-First Search with State Tracking

The key observation is that this is fundamentally a shortest path problem on an unweighted graph.

Each move costs exactly one step, which makes Breadth-First Search ideal because BFS guarantees that the first time we reach the target, we have used the minimum number of steps.

The challenge is that the state is not just the current position.

The full state consists of:

• current row
• current column
• remaining obstacle eliminations

Why is this necessary?

Suppose we reach the same cell twice:

• once with 0 eliminations remaining
• once with 3 eliminations remaining

These are not equivalent states. The second state is strictly more powerful because it allows future obstacles to be removed.

Therefore, we cannot use a simple visited[row][col] structure.

Instead, we store the maximum remaining eliminations seen for each cell. If we revisit a cell with fewer remaining eliminations than before, that state is dominated and can be skipped.

This optimization dramatically reduces redundant exploration.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all possible paths recursively
Optimal BFS	O(m * n * k)	O(m * n * k)	BFS over augmented state space

Algorithm Walkthrough

1. Initialize dimensions and handle trivial cases.

If the grid contains only one cell, we are already at the destination, so the answer is 0. 2. Apply an important optimization.

The shortest possible path in an m x n grid without detours is:

m + n - 2

If k is at least this value, then we can always walk directly toward the destination while removing any obstacles encountered.

In that case, we immediately return:

m + n - 2 3. Create the BFS queue.

Each queue entry stores:

• current row
• current column
• remaining eliminations
• steps taken so far

We begin with:

• position (0,0)
• k eliminations remaining
• 0 steps

4. Track visited states efficiently.

Instead of storing every (row, col, remaining_k) combination separately, we maintain:

visited[row][col] = maximum remaining eliminations seen

This works because reaching the same cell with fewer remaining eliminations can never be better. 5. Perform BFS level traversal.

Repeatedly pop states from the queue.

For each state:

• try all four directions
• skip out-of-bounds cells
• determine whether entering the next cell consumes an elimination

6. Update remaining eliminations.

If the next cell contains an obstacle:

• subtract one from remaining eliminations

If remaining eliminations become negative:

• this move is invalid

7. Check for destination.

If the next cell is the bottom-right corner:

• return steps + 1

Because BFS explores states in increasing order of distance, this is guaranteed to be the shortest path. 8. Prune dominated states.

Before pushing a new state into the queue:

• compare its remaining eliminations against the best previously recorded value for that cell

If we already reached the cell with an equal or larger remaining budget:

• skip this state

Otherwise:

• update visited
• enqueue the new state

9. If BFS finishes without reaching the target:

return -1

Why it works

Breadth-First Search explores states in order of increasing path length. Therefore, the first time the destination is reached must correspond to the minimum number of steps.

The pruning rule is also correct because a state with more remaining eliminations strictly dominates one with fewer eliminations at the same position. Any future path available from the weaker state is also available from the stronger state.

Together, these properties guarantee both correctness and efficiency.

Python Solution

from collections import deque
from typing import List

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        rows = len(grid)
        cols = len(grid[0])

        if rows == 1 and cols == 1:
            return 0

        # If we can eliminate enough obstacles to walk directly
        # to the destination, return the Manhattan distance.
        if k >= rows + cols - 2:
            return rows + cols - 2

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        queue = deque([(0, 0, k, 0)])

        # visited[row][col] stores the maximum remaining
        # eliminations seen at this cell.
        visited = [[-1] * cols for _ in range(rows)]
        visited[0][0] = k

        while queue:
            row, col, remaining_k, steps = queue.popleft()

            for dr, dc in directions:
                new_row = row + dr
                new_col = col + dc

                if (
                    new_row < 0
                    or new_row >= rows
                    or new_col < 0
                    or new_col >= cols
                ):
                    continue

                new_remaining_k = remaining_k - grid[new_row][new_col]

                if new_remaining_k < 0:
                    continue

                if new_row == rows - 1 and new_col == cols - 1:
                    return steps + 1

                # Skip dominated states.
                if visited[new_row][new_col] >= new_remaining_k:
                    continue

                visited[new_row][new_col] = new_remaining_k

                queue.append(
                    (
                        new_row,
                        new_col,
                        new_remaining_k,
                        steps + 1,
                    )
                )

        return -1

The implementation begins by extracting the grid dimensions and handling the single-cell case. This avoids unnecessary BFS work when the start is already the destination.

The next optimization checks whether k is large enough to ignore all obstacles along a direct shortest route. Since the shortest geometric distance is always rows + cols - 2, having at least that many eliminations guarantees success along a direct path.

The BFS queue stores complete traversal state:

• current coordinates
• remaining eliminations
• current path length

A deque is used because BFS repeatedly removes elements from the front and appends new states to the back in constant time.

The visited matrix stores the best remaining elimination count observed for each cell. This is the key optimization that prevents redundant exploration.

During traversal, each neighbor is examined:

• invalid coordinates are skipped
• obstacles consume one elimination
• states with negative remaining eliminations are discarded

If the destination is reached, the algorithm immediately returns the current distance plus one step.

Before enqueuing a new state, the algorithm checks whether the same cell has already been reached with an equal or better remaining elimination count. If so, the new state is dominated and ignored.

If BFS exhausts all states without finding the destination, the function returns -1.

Go Solution

package main

import "container/list"

type State struct {
	row        int
	col        int
	remainingK int
	steps      int
}

func shortestPath(grid [][]int, k int) int {
	rows := len(grid)
	cols := len(grid[0])

	if rows == 1 && cols == 1 {
		return 0
	}

	if k >= rows+cols-2 {
		return rows + cols - 2
	}

	directions := [][]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	queue := list.New()
	queue.PushBack(State{0, 0, k, 0})

	visited := make([][]int, rows)
	for i := 0; i < rows; i++ {
		visited[i] = make([]int, cols)

		for j := 0; j < cols; j++ {
			visited[i][j] = -1
		}
	}

	visited[0][0] = k

	for queue.Len() > 0 {
		front := queue.Front()
		queue.Remove(front)

		current := front.Value.(State)

		for _, dir := range directions {
			newRow := current.row + dir[0]
			newCol := current.col + dir[1]

			if newRow < 0 || newRow >= rows ||
				newCol < 0 || newCol >= cols {
				continue
			}

			newRemainingK := current.remainingK - grid[newRow][newCol]

			if newRemainingK < 0 {
				continue
			}

			if newRow == rows-1 && newCol == cols-1 {
				return current.steps + 1
			}

			if visited[newRow][newCol] >= newRemainingK {
				continue
			}

			visited[newRow][newCol] = newRemainingK

			queue.PushBack(
				State{
					newRow,
					newCol,
					newRemainingK,
					current.steps + 1,
				},
			)
		}
	}

	return -1
}

The Go solution follows the same algorithmic structure as the Python implementation.

A custom State struct is used to store BFS state cleanly. The BFS queue is implemented using Go's container/list package because it provides efficient front removal and back insertion.

Unlike Python, Go does not provide dynamic tuple structures, so explicit struct fields improve readability and type safety.

The visited matrix is initialized manually with -1 values because Go slices default to 0, which would incorrectly imply that cells had already been visited with zero eliminations remaining.

No integer overflow concerns exist because all values remain small under the problem constraints.

Worked Examples

Example 1

grid =
[
  [0,0,0],
  [1,1,0],
  [0,0,0],
  [0,1,1],
  [0,0,0]
]

k = 1

Target cell is (4,2).

Initial queue:

Queue State	Meaning
(0,0,1,0)	row=0, col=0, remaining_k=1, steps=0

Initial visited:

Cell	Best Remaining k
(0,0)	1

Step 1

Pop (0,0,1,0).

Possible moves:

Next Cell	Obstacle?	New k	Valid?
(1,0)	Yes	0	Yes
(0,1)	No	1	Yes

Queue becomes:

Queue
(1,0,0,1)
(0,1,1,1)

Step 2

Pop (1,0,0,1).

Possible moves:

Next Cell	Obstacle?	New k	Valid?
(2,0)	No	0	Yes
(1,1)	Yes	-1	No

Queue:

Queue
(0,1,1,1)
(2,0,0,2)

Step 3

Pop (0,1,1,1).

Possible moves:

Next Cell	Obstacle?	New k
(0,2)	No	1
(1,1)	Yes	0

Queue expands further.

Eventually BFS reaches:

(4,2)

after 6 steps.

Returned answer:

6

Example 2

grid =
[
  [0,1,1],
  [1,1,1],
  [1,0,0]
]

k = 1

The destination cannot be reached because every valid route requires eliminating at least two obstacles.

BFS explores all reachable states and eventually exhausts the queue.

Returned answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n * k)	Each state may be processed once
Space	O(m * n * k)	BFS queue and state tracking

The algorithm explores states defined by:

(row, col, remaining_k)

There are at most:

m * n * (k + 1)

distinct states.

For each state, we attempt four directional moves, which is constant work. Therefore, total runtime is proportional to the number of reachable states.

The queue and visited tracking together also require storage proportional to the total state space.

Test Cases

from typing import List

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        from collections import deque

        rows = len(grid)
        cols = len(grid[0])

        if rows == 1 and cols == 1:
            return 0

        if k >= rows + cols - 2:
            return rows + cols - 2

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        queue = deque([(0, 0, k, 0)])

        visited = [[-1] * cols for _ in range(rows)]
        visited[0][0] = k

        while queue:
            row, col, remaining_k, steps = queue.popleft()

            for dr, dc in directions:
                nr = row + dr
                nc = col + dc

                if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                    continue

                new_k = remaining_k - grid[nr][nc]

                if new_k < 0:
                    continue

                if nr == rows - 1 and nc == cols - 1:
                    return steps + 1

                if visited[nr][nc] >= new_k:
                    continue

                visited[nr][nc] = new_k

                queue.append((nr, nc, new_k, steps + 1))

        return -1

solution = Solution()

# Example 1
assert solution.shortestPath(
    [
        [0,0,0],
        [1,1,0],
        [0,0,0],
        [0,1,1],
        [0,0,0]
    ],
    1
) == 6  # standard example with one elimination

# Example 2
assert solution.shortestPath(
    [
        [0,1,1],
        [1,1,1],
        [1,0,0]
    ],
    1
) == -1  # impossible with insufficient eliminations

# Single cell grid
assert solution.shortestPath([[0]], 1) == 0  # already at destination

# No obstacles
assert solution.shortestPath(
    [
        [0,0],
        [0,0]
    ],
    0
) == 2  # direct shortest path

# Must eliminate exactly one obstacle
assert solution.shortestPath(
    [
        [0,1],
        [1,0]
    ],
    1
) == 2  # elimination required

# Large k enables direct path
assert solution.shortestPath(
    [
        [0,1,1],
        [1,1,0],
        [0,0,0]
    ],
    10
) == 4  # k large enough for Manhattan path

# Path exists without eliminations
assert solution.shortestPath(
    [
        [0,0,0],
        [1,1,0],
        [0,0,0]
    ],
    0
) == 4  # normal BFS shortest route

# Complex revisiting scenario
assert solution.shortestPath(
    [
        [0,1,0],
        [0,1,0],
        [0,0,0]
    ],
    1
) == 4  # revisiting with better remaining k matters

# Impossible even with some eliminations
assert solution.shortestPath(
    [
        [0,1,1],
        [1,1,1],
        [1,1,0]
    ],
    2
) == -1  # still blocked

print("All test cases passed!")

Test	Why
Example 1	Validates standard obstacle elimination behavior
Example 2	Confirms impossible paths return -1
Single cell grid	Tests trivial base case
No obstacles	Ensures ordinary BFS behavior works
Exact elimination needed	Verifies obstacle removal logic
Large k	Tests optimization for direct Manhattan path
Path without eliminations	Confirms algorithm works with k = 0
Revisiting scenario	Validates state dominance pruning
Impossible dense grid	Ensures exhaustive BFS termination

Edge Cases

One important edge case is a single-cell grid such as [[0]]. In this scenario, the start and destination are the same cell. A buggy implementation might incorrectly perform BFS and return 1 instead of 0. The implementation handles this immediately with an early return before any traversal begins.

Another subtle case occurs when the same cell is reached multiple times with different remaining elimination counts. A naive visited structure based only on coordinates would incorrectly prune potentially optimal states. For example, reaching a cell later with more remaining eliminations may enable a shorter future route. The implementation solves this by storing the maximum remaining eliminations observed for each cell.

A third important edge case happens when k is extremely large relative to the grid dimensions. Without optimization, BFS would still explore a massive state space unnecessarily. The implementation recognizes that if k >= rows + cols - 2, we can always move directly to the destination while eliminating obstacles along the way. In that case, the answer is simply the Manhattan distance.

Another tricky case involves impossible grids where all routes require more eliminations than available. A flawed implementation might loop indefinitely or incorrectly assume every grid is solvable. This solution naturally handles such cases because BFS eventually exhausts all reachable states and returns -1.

Finally, boundary movement is a common source of bugs in grid problems. Every neighbor expansion must verify row and column limits before accessing the grid. The implementation explicitly checks bounds before processing neighbors, preventing invalid memory access and incorrect traversal.