LeetCode Problem 499

Difficulty: 🔴 Hard
Topics: Array, String, Depth-First Search, Breadth-First Search, Graph Theory, Heap (Priority Queue), Matrix, Shortest Path

Solution

LeetCode 499 - The Maze III

Problem Understanding

This problem extends the mechanics introduced in earlier Maze problems, but adds two important complications. First, we are no longer looking for a simple reachable or unreachable answer. Instead, we must find the shortest path by travel distance. Second, if multiple shortest paths exist, we must return the lexicographically smallest instruction string.

The maze is represented as a two-dimensional grid where 0 indicates an empty space and 1 indicates a wall. A ball starts at a given position, and there is also a hole somewhere in the maze. The ball can roll in one of four directions: up, down, left, or right.

The important movement rule is that the ball does not stop after moving one cell. Once a direction is chosen, the ball continues rolling until one of two things happens:

1. It hits a wall, in which case it stops on the previous valid cell.
2. It falls into the hole, in which case movement ends immediately.

The objective is to produce a sequence of directions such that:

• The ball eventually falls into the hole.
• The total traveled distance is minimized.
• If multiple paths have the same minimum distance, choose the lexicographically smallest instruction string.

The returned value is the instruction string consisting of characters:

• 'u' for up
• 'd' for down
• 'l' for left
• 'r' for right

If the hole cannot be reached, the result must be "impossible".

The constraints are important because the maze dimensions can be as large as 100 x 100. That means there can be up to 10,000 cells. A naive exhaustive search over all possible rolling sequences would quickly become infeasible. We need an algorithm that efficiently avoids revisiting worse states.

Several edge cases are especially important:

• The ball may roll past the hole unless we explicitly stop when the hole is encountered during movement.
• Multiple paths may have the same shortest distance, requiring careful lexicographical comparison.
• A cell may be revisited with a better distance or a lexicographically smaller path.
• The ball cannot stop arbitrarily, it only stops at walls or inside the hole.
• The hole may be unreachable even though the maze contains many open spaces.

This combination of shortest path computation and lexicographical tie-breaking strongly suggests a graph shortest path algorithm such as Dijkstra's algorithm.

Approaches

Brute Force Approach

A brute-force solution would recursively explore every possible sequence of rolling directions from the starting position. At each stopping point, the algorithm would attempt rolling in all four directions and continue until either the hole is reached or all possibilities are exhausted.

This approach is correct because it eventually enumerates every possible valid movement sequence. However, it is computationally impractical because the same stopping positions can be revisited many times with different path strings and distances.

The number of possible movement sequences grows exponentially with the number of reachable stopping points. Since each state can branch into four directions repeatedly, the search space becomes enormous even for moderately sized mazes.

Additionally, lexicographical ordering complicates pruning because two paths with identical distances may still need comparison.

Optimal Approach

The key insight is that this is fundamentally a weighted shortest path problem.

Each stopping position in the maze can be viewed as a graph node. Rolling in a direction creates an edge whose weight equals the number of cells traveled before stopping or falling into the hole.

Since movement costs are non-uniform, ordinary BFS is insufficient. BFS only guarantees correctness when all edge weights are equal. Here, one roll might travel one cell while another travels twenty.

Dijkstra's algorithm is ideal because:

• It computes shortest weighted paths.
• It naturally handles revisiting nodes when a better path is discovered.
• A priority queue allows exploration in increasing order of total distance.
• We can extend the comparison logic to include lexicographical ordering when distances tie.

The algorithm stores:

• Current total distance
• Current path string
• Current coordinates

The priority queue prioritizes:

1. Smaller distance
2. Lexicographically smaller path string

This guarantees that the first time we remove the hole from the priority queue, we have the optimal answer.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all possible rolling sequences
Optimal	O(mn log(mn) × max(m, n))	O(mn)	Dijkstra's algorithm with lexicographical tie-breaking

Algorithm Walkthrough

1. Initialize a priority queue containing the starting position with distance 0 and an empty instruction string.
2. Create a dictionary or matrix that records the best known state for every cell. A state consists of:

• Minimum distance to reach the cell
• Lexicographically smallest path for that distance

3. Define the four possible rolling directions:

• Up: (-1, 0, 'u')
• Down: (1, 0, 'd')
• Left: (0, -1, 'l')
• Right: (0, 1, 'r')

4. Repeatedly extract the best state from the priority queue. The priority queue orders states first by total distance and then by lexicographical path string.

5. If the current position is the hole, immediately return the current path string. Because of Dijkstra ordering, this is guaranteed to be the shortest path and lexicographically smallest among all shortest paths.

6. For each direction:

7. Start from the current cell.

8. Roll continuously in that direction.

9. Count how many cells were traversed.

10. Stop if:

• A wall is reached, or
• The hole is encountered

5. Compute:

• New total distance
• New path string

7. Compare the newly discovered state against the best known state for the stopping position.

• If the new distance is smaller, update it.
• If the distance is equal but the path string is lexicographically smaller, also update it.

8. Push the improved state into the priority queue.
9. Continue until:

• The hole is found, or
• The priority queue becomes empty

10. If the queue becomes empty without reaching the hole, return "impossible".

Why it works

Dijkstra's algorithm guarantees that nodes are processed in non-decreasing order of shortest known distance. By extending the priority comparison to include lexicographical ordering, we ensure that among all shortest paths, the lexicographically smallest one is processed first.

Because every edge weight is non-negative, once the hole is removed from the priority queue, no better solution can exist later.

Python Solution

from typing import List
import heapq

class Solution:
    def findShortestWay(
        self,
        maze: List[List[int]],
        ball: List[int],
        hole: List[int]
    ) -> str:

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

        directions = [
            (-1, 0, 'u'),
            (1, 0, 'd'),
            (0, -1, 'l'),
            (0, 1, 'r')
        ]

        priority_queue = [(0, "", ball[0], ball[1])]

        best = {
            (ball[0], ball[1]): (0, "")
        }

        while priority_queue:
            distance, path, row, col = heapq.heappop(priority_queue)

            if [row, col] == hole:
                return path

            if best[(row, col)] < (distance, path):
                continue

            for dr, dc, direction_char in directions:
                current_row = row
                current_col = col
                steps = 0

                while True:
                    next_row = current_row + dr
                    next_col = current_col + dc

                    if (
                        next_row < 0 or
                        next_row >= rows or
                        next_col < 0 or
                        next_col >= cols or
                        maze[next_row][next_col] == 1
                    ):
                        break

                    current_row = next_row
                    current_col = next_col
                    steps += 1

                    if [current_row, current_col] == hole:
                        break

                new_distance = distance + steps
                new_path = path + direction_char

                state = (current_row, current_col)

                if (
                    state not in best or
                    (new_distance, new_path) < best[state]
                ):
                    best[state] = (new_distance, new_path)

                    heapq.heappush(
                        priority_queue,
                        (
                            new_distance,
                            new_path,
                            current_row,
                            current_col
                        )
                    )

        return "impossible"

The implementation begins by defining the maze dimensions and the four possible rolling directions. Each direction includes both coordinate movement and the corresponding instruction character.

A priority queue is used to implement Dijkstra's algorithm. Each queue entry stores:

• Total distance traveled
• Path string
• Current row
• Current column

Python's heap ordering naturally prioritizes tuples lexicographically, so (distance, path) automatically enforces the correct ordering.

The best dictionary stores the optimal known state for each cell. A state is considered better if:

• It has a smaller distance, or
• It has the same distance but a lexicographically smaller path

The rolling simulation is the core of the problem. For each direction, the ball continues moving until it either hits a wall or falls into the hole. Importantly, the hole check occurs during movement, not only after stopping, because the ball immediately disappears into the hole.

Whenever a better state is found, it is inserted into the priority queue for future exploration.

If the hole is never reached, the algorithm returns "impossible".

Go Solution

package main

import (
	"container/heap"
)

type State struct {
	dist int
	path string
	row  int
	col  int
}

type PriorityQueue []State

func (pq PriorityQueue) Len() int {
	return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
	if pq[i].dist == pq[j].dist {
		return pq[i].path < pq[j].path
	}
	return pq[i].dist < pq[j].dist
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(State))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)

	item := old[n-1]
	*pq = old[:n-1]

	return item
}

func findShortestWay(maze [][]int, ball []int, hole []int) string {
	rows := len(maze)
	cols := len(maze[0])

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

	dirChars := []string{"u", "d", "l", "r"}

	pq := &PriorityQueue{}
	heap.Init(pq)

	heap.Push(pq, State{
		dist: 0,
		path: "",
		row:  ball[0],
		col:  ball[1],
	})

	best := make(map[[2]int]State)

	startKey := [2]int{ball[0], ball[1]}
	best[startKey] = State{
		dist: 0,
		path: "",
	}

	for pq.Len() > 0 {
		current := heap.Pop(pq).(State)

		if current.row == hole[0] && current.col == hole[1] {
			return current.path
		}

		key := [2]int{current.row, current.col}

		bestState := best[key]

		if current.dist > bestState.dist ||
			(current.dist == bestState.dist &&
				current.path > bestState.path) {
			continue
		}

		for i := 0; i < 4; i++ {
			dr := directions[i][0]
			dc := directions[i][1]

			row := current.row
			col := current.col
			steps := 0

			for {
				nextRow := row + dr
				nextCol := col + dc

				if nextRow < 0 ||
					nextRow >= rows ||
					nextCol < 0 ||
					nextCol >= cols ||
					maze[nextRow][nextCol] == 1 {
					break
				}

				row = nextRow
				col = nextCol
				steps++

				if row == hole[0] && col == hole[1] {
					break
				}
			}

			newDist := current.dist + steps
			newPath := current.path + dirChars[i]

			newKey := [2]int{row, col}

			prev, exists := best[newKey]

			if !exists ||
				newDist < prev.dist ||
				(newDist == prev.dist &&
					newPath < prev.path) {

				best[newKey] = State{
					dist: newDist,
					path: newPath,
				}

				heap.Push(pq, State{
					dist: newDist,
					path: newPath,
					row:  row,
					col:  col,
				})
			}
		}
	}

	return "impossible"
}

The Go implementation follows the same algorithmic structure as the Python solution, but several language-specific details differ.

Go does not provide a built-in priority queue, so the container/heap package is used. This requires implementing the heap.Interface, including methods such as Len, Less, Swap, Push, and Pop.

The priority ordering is explicitly implemented inside the Less method. Distance is compared first, and path strings are compared second for lexicographical ordering.

Go maps require comparable keys, so coordinates are stored as fixed-size arrays [2]int instead of slices.

Unlike Python tuples, Go structs do not support automatic comparison, so all tie-breaking logic must be implemented manually.

Worked Examples

Example 1

maze =
[
  [0,0,0,0,0],
  [1,1,0,0,1],
  [0,0,0,0,0],
  [0,1,0,0,1],
  [0,1,0,0,0]
]

ball = [4,3]
hole = [0,1]

The priority queue initially contains:

Distance	Path	Position
0	""	(4,3)

From (4,3):

Direction	Final Position	Steps	Path
up	(0,3)	4	"u"
left	(4,2)	1	"l"
right	(4,4)	1	"r"

The queue becomes:

Distance	Path	Position
1	"l"	(4,2)
1	"r"	(4,4)
4	"u"	(0,3)

The lexicographically smaller path "l" is processed first.

From (4,2):

Direction	Final Position	Steps	Path
up	(0,2)	4	"lu"
left	(4,2)	0	ignored

Eventually, the algorithm reaches the hole with path "lul" and distance 6.

Another path "ul" also has distance 6, but "lul" is lexicographically smaller because 'l' < 'u'.

The returned answer is:

"lul"

Example 2

ball = [4,3]
hole = [3,0]

The algorithm explores all reachable stopping points, but no rolling sequence lands exactly on the hole.

Since the priority queue eventually becomes empty, the algorithm returns:

"impossible"

Example 3

ball = [0,4]
hole = [3,5]

The algorithm explores paths in increasing distance order.

A shortest valid sequence discovered is:

"dldr"

The total traveled distance is minimal among all possible valid routes.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(mn log(mn) × max(m, n))	Each cell may be processed multiple times, and each roll can traverse an entire row or column
Space	O(mn)	Priority queue and best-state storage

The maze contains at most m × n stopping positions. Every priority queue operation costs O(log(mn)). For each processed state, the algorithm may roll across an entire row or column, which costs up to O(max(m, n)).

The space complexity comes from storing the priority queue and the best known state for each reachable cell.

Test Cases

from typing import List

class Solution:
    def findShortestWay(
        self,
        maze: List[List[int]],
        ball: List[int],
        hole: List[int]
    ) -> str:

        import heapq

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

        directions = [
            (-1, 0, 'u'),
            (1, 0, 'd'),
            (0, -1, 'l'),
            (0, 1, 'r')
        ]

        pq = [(0, "", ball[0], ball[1])]

        best = {(ball[0], ball[1]): (0, "")}

        while pq:
            dist, path, row, col = heapq.heappop(pq)

            if [row, col] == hole:
                return path

            if best[(row, col)] < (dist, path):
                continue

            for dr, dc, ch in directions:
                r = row
                c = col
                steps = 0

                while True:
                    nr = r + dr
                    nc = c + dc

                    if (
                        nr < 0 or
                        nr >= rows or
                        nc < 0 or
                        nc >= cols or
                        maze[nr][nc] == 1
                    ):
                        break

                    r = nr
                    c = nc
                    steps += 1

                    if [r, c] == hole:
                        break

                new_dist = dist + steps
                new_path = path + ch

                if (
                    (r, c) not in best or
                    (new_dist, new_path) < best[(r, c)]
                ):
                    best[(r, c)] = (new_dist, new_path)
                    heapq.heappush(
                        pq,
                        (new_dist, new_path, r, c)
                    )

        return "impossible"

solution = Solution()

assert solution.findShortestWay(
    [
        [0,0,0,0,0],
        [1,1,0,0,1],
        [0,0,0,0,0],
        [0,1,0,0,1],
        [0,1,0,0,0]
    ],
    [4,3],
    [0,1]
) == "lul"  # lexicographically smallest shortest path

assert solution.findShortestWay(
    [
        [0,0,0,0,0],
        [1,1,0,0,1],
        [0,0,0,0,0],
        [0,1,0,0,1],
        [0,1,0,0,0]
    ],
    [4,3],
    [3,0]
) == "impossible"  # unreachable hole

assert solution.findShortestWay(
    [
        [0,0,0,0,0,0,0],
        [0,0,1,0,0,1,0],
        [0,0,0,0,1,0,0],
        [0,0,0,0,0,0,1]
    ],
    [0,4],
    [3,5]
) == "dldr"  # standard shortest path

assert solution.findShortestWay(
    [
        [0,0,0],
        [0,1,0],
        [0,0,0]
    ],
    [2,0],
    [0,2]
) == "ru"  # simple two-move solution

assert solution.findShortestWay(
    [
        [0,0,0],
        [0,1,0],
        [0,0,0]
    ],
    [0,0],
    [2,2]
) == "dr"  # corner-to-corner traversal

assert solution.findShortestWay(
    [
        [0,0],
        [0,0]
    ],
    [0,0],
    [1,1]
) == "dr"  # smallest open grid

assert solution.findShortestWay(
    [
        [0,1,0],
        [0,1,0],
        [0,1,0]
    ],
    [0,0],
    [2,2]
) == "impossible"  # disconnected regions

Test	Why
Example 1	Validates shortest path with lexicographical tie-breaking
Example 2	Validates unreachable hole handling
Example 3	Validates standard weighted shortest path behavior
Small 3x3 maze	Tests simple directional rolling
Corner-to-corner traversal	Verifies long continuous rolling
Smallest open grid	Tests minimal valid maze
Disconnected regions	Ensures impossible cases are detected correctly

Edge Cases

One important edge case occurs when the ball rolls over the hole before reaching a wall. A common bug is to only check whether the final stopping position equals the hole. That approach is incorrect because the ball immediately falls into the hole as soon as it passes over it. The implementation handles this by checking for the hole during each rolling step.

Another critical edge case involves multiple shortest paths with identical travel distances. Standard shortest path algorithms typically only compare distances, but this problem additionally requires the lexicographically smallest instruction string. The implementation handles this by storing both distance and path in the priority queue ordering and in the best-state comparison logic.

A third subtle case occurs when a cell is revisited with a better path. Even if a cell was processed earlier, a later route might produce either:

• A shorter distance, or
• The same distance but a lexicographically smaller path

The implementation correctly updates the stored state whenever either improvement occurs.

A fourth important case involves rolling into dead ends or remaining stationary. Some directions may immediately hit a wall and produce zero movement. The algorithm safely handles these cases because the resulting state will not improve the existing best state, preventing unnecessary processing or infinite loops.

Finally, unreachable holes are an essential scenario. The maze may contain many open cells while still making the hole inaccessible due to wall placement and rolling constraints. The algorithm correctly returns "impossible" once the priority queue is exhausted without reaching the hole.