LeetCode 490 - The Maze

This problem asks us to determine whether a rolling ball can stop exactly at a destination cell inside a maze. The maze is represented as a two-dimensional grid where: - 0 represents an empty space the ball can roll through - 1 represents a wall The important detail is that…

leetcodemediumarraydepth-first-searchbreadth-first-searchmatrix

LeetCode Problem 490

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Matrix

Solution

Problem Understanding

This problem asks us to determine whether a rolling ball can stop exactly at a destination cell inside a maze.

The maze is represented as a two-dimensional grid where:

  • 0 represents an empty space the ball can roll through
  • 1 represents a wall

The important detail is that the ball does not move one cell at a time. Instead, once the ball starts moving in a direction, it keeps rolling until it hits a wall. Only after stopping can it choose another direction.

This changes the problem significantly from a standard grid traversal problem. In a normal BFS or DFS on a matrix, we would move one step at a time. Here, every move continues until collision with a wall.

The input consists of:

  • maze, the grid
  • start, the starting coordinates of the ball
  • destination, the target coordinates

The output should be:

  • true if the ball can stop exactly at the destination
  • false otherwise

A critical subtlety is that merely passing through the destination is not enough. The ball must stop there. If the destination lies in the middle of a rolling path and the ball continues moving beyond it until a wall is reached, that path does not count.

The constraints tell us several important things:

  • The maze dimensions are at most 100 x 100
  • There can be up to 10,000 cells total
  • A graph traversal solution is expected
  • Exponential brute force approaches would be too slow
  • We need to avoid revisiting states repeatedly

The problem guarantees that:

  • Borders are walls, which simplifies rolling logic
  • Start and destination are valid empty cells
  • Start and destination are different
  • There are at least two empty cells

Several edge cases are important:

  • The destination may be reachable geometrically but impossible to stop on
  • The maze may contain cycles, requiring visited tracking
  • Long corridors can cause repeated rolling computations
  • The ball may revisit the same stopping position from different paths
  • A maze with many open spaces can create infinite traversal loops if visited states are not tracked correctly

Approaches

Brute Force Approach

A brute force solution would attempt every possible rolling sequence recursively without tracking visited stopping positions.

From every stopping point, we would:

  1. Roll in all four directions
  2. Continue until hitting a wall
  3. Recursively explore from the new stopping position

This approach is correct because it eventually explores every possible path the ball can take.

However, it is inefficient because the maze may contain cycles. The ball can revisit the same stopping position repeatedly through different paths. Without remembering previously explored states, the algorithm can loop indefinitely or perform massive redundant work.

For example, in an open maze, the ball might bounce between the same few stopping positions endlessly.

Optimal Approach

The key insight is that the only meaningful states are stopping positions.

The ball cannot make decisions while rolling. Decisions only occur after hitting a wall and stopping. Therefore, instead of treating every traversed cell as a state, we treat each stopping coordinate as a graph node.

This transforms the problem into a graph traversal problem:

  • Each stopping position is a node
  • A valid roll between two stopping positions is an edge

We can then use either DFS or BFS with a visited set to avoid revisiting stopping positions.

Whenever we process a position:

  1. Roll in all four directions
  2. Compute the next stopping position
  3. If that position has not been visited, explore it

This guarantees that every reachable stopping position is explored at most once.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Repeatedly explores the same stopping states
Optimal DFS/BFS O(m × n × max(m, n)) O(m × n) Visits each stopping position once

Algorithm Walkthrough

We will use Breadth-First Search, although Depth-First Search works equally well.

Step 1: Initialize the traversal

Create:

  • A queue for BFS
  • A visited set or matrix
  • The four movement directions

We begin by adding the starting position into the queue and marking it visited.

We track visited stopping positions because revisiting them provides no new information and can create infinite loops.

Step 2: Process positions level by level

While the queue is not empty:

  1. Remove the current stopping position
  2. Check whether it equals the destination
  3. If so, return True

This means the ball can stop exactly at the destination.

Step 3: Roll in each direction

For every direction:

  1. Start from the current position
  2. Continue moving until the next move would hit a wall
  3. Stop at the last valid empty cell

This simulates the rolling behavior exactly as described in the problem.

The rolling loop is the core of the problem:

while within_bounds and next_cell_is_empty:
    move_forward

The final position after this loop is a valid stopping point.

Step 4: Explore unvisited stopping points

If the stopping position has not been visited:

  1. Mark it visited
  2. Add it to the queue

This ensures each stopping node is processed only once.

Step 5: Finish traversal

If the queue becomes empty without reaching the destination, return False.

This means no sequence of valid rolls allows the ball to stop at the destination.

Why it works

The algorithm works because it systematically explores every reachable stopping position exactly once.

The invariant is:

Every position added to the queue is a valid stopping point reachable from the start.

Since every possible roll from every reachable stopping point is explored, the algorithm eventually examines all reachable states. If the destination is reachable as a stopping point, it will be discovered. If not, the traversal will terminate after exhausting all possibilities.

Python Solution

from collections import deque
from typing import List

class Solution:
    def hasPath(
        self,
        maze: List[List[int]],
        start: List[int],
        destination: List[int]
    ) -> bool:
        
        rows = len(maze)
        cols = len(maze[0])

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

        queue = deque([tuple(start)])
        visited = set()
        visited.add(tuple(start))

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

            if [row, col] == destination:
                return True

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

                while (
                    0 <= new_row + dr < rows
                    and 0 <= new_col + dc < cols
                    and maze[new_row + dr][new_col + dc] == 0
                ):
                    new_row += dr
                    new_col += dc

                if (new_row, new_col) not in visited:
                    visited.add((new_row, new_col))
                    queue.append((new_row, new_col))

        return False

The implementation begins by computing the maze dimensions and defining the four movement directions.

A BFS queue stores stopping positions that still need exploration. The visited set prevents revisiting already explored stopping points.

For every dequeued position, the algorithm checks whether it matches the destination. If it does, the answer is immediately True.

The most important section is the rolling simulation. For each direction, the algorithm repeatedly advances the ball until the next step would either:

  • Move outside the maze
  • Hit a wall

The resulting coordinates represent the stopping point after rolling.

If this stopping position has not been visited before, it is added to the queue for future exploration.

Eventually, either the destination is found or all reachable stopping positions are exhausted.

Go Solution

package main

import "container/list"

func hasPath(maze [][]int, start []int, destination []int) bool {
	rows := len(maze)
	cols := len(maze[0])

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

	queue := list.New()
	queue.PushBack([]int{start[0], start[1]})

	visited := make(map[[2]int]bool)
	visited[[2]int{start[0], start[1]}] = true

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

		position := front.Value.([]int)
		row, col := position[0], position[1]

		if row == destination[0] && col == destination[1] {
			return true
		}

		for _, dir := range directions {
			dr, dc := dir[0], dir[1]

			newRow := row
			newCol := col

			for (
				newRow+dr >= 0 &&
					newRow+dr < rows &&
					newCol+dc >= 0 &&
					newCol+dc < cols &&
					maze[newRow+dr][newCol+dc] == 0) {

				newRow += dr
				newCol += dc
			}

			key := [2]int{newRow, newCol}

			if !visited[key] {
				visited[key] = true
				queue.PushBack([]int{newRow, newCol})
			}
		}
	}

	return false
}

The Go implementation follows the same logic as the Python solution, but there are some language-specific differences.

Go does not have a built-in deque structure like Python's collections.deque, so we use container/list as the BFS queue.

For visited tracking, Go maps cannot use slices as keys because slices are not comparable. Instead, we use fixed-size arrays of type [2]int.

The rolling logic remains identical to the Python version.

Since the constraints are small, integer overflow is not a concern.

Worked Examples

Example 1

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

start = [0,4]
destination = [4,4]

Initial State

Variable Value
Queue [(0,4)]
Visited {(0,4)}

Process (0,4)

Direction Final Stop
Down (2,4)
Up (0,4)
Right (0,4)
Left (0,3)

New queue contents:

Queue Visited
[(2,4), (0,3)] {(0,4), (2,4), (0,3)}

Process (2,4)

Direction Final Stop
Down (2,4)
Up (0,4)
Right (2,4)
Left (2,4)

No new states added.

Process (0,3)

Direction Final Stop
Down (1,3)
Up (0,3)
Right (0,4)
Left (0,3)

Queue becomes:

Queue
[(1,3)]

The traversal continues exploring stopping positions until eventually reaching (4,4).

The algorithm returns True.

Example 2

destination = [3,2]

The ball can pass through (3,2) but cannot stop there because there is no wall configuration allowing the roll to terminate at that position.

The BFS explores all reachable stopping points and never dequeues (3,2).

The algorithm returns False.

Example 3

start = [4,3]
destination = [0,1]

The BFS explores all reachable stopping positions but never reaches (0,1) as a stopping point.

Even though nearby paths exist, the rolling mechanics prevent stopping exactly there.

The algorithm returns False.

Complexity Analysis

Measure Complexity Explanation
Time O(m × n × max(m, n)) Each stopping position may roll across an entire row or column
Space O(m × n) Queue and visited set can store every cell

The maze contains at most m × n stopping positions.

For each processed position, we attempt four rolls. A single roll can traverse up to max(m, n) cells in the worst case.

Therefore, the total time complexity is:

O(m × n × max(m, n))

The visited set and BFS queue together can contain at most all cells in the maze, giving:

O(m × n)

space complexity.

Test Cases

from typing import List

class Solution:
    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
        from collections import deque

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

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

        queue = deque([tuple(start)])
        visited = {tuple(start)}

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

            if [row, col] == destination:
                return True

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

                while (
                    0 <= nr + dr < rows
                    and 0 <= nc + dc < cols
                    and maze[nr + dr][nc + dc] == 0
                ):
                    nr += dr
                    nc += dc

                if (nr, nc) not in visited:
                    visited.add((nr, nc))
                    queue.append((nr, nc))

        return False

solution = Solution()

# Example 1, reachable destination
assert solution.hasPath(
    [[0,0,1,0,0],
     [0,0,0,0,0],
     [0,0,0,1,0],
     [1,1,0,1,1],
     [0,0,0,0,0]],
    [0,4],
    [4,4]
) == True

# Example 2, cannot stop at destination
assert solution.hasPath(
    [[0,0,1,0,0],
     [0,0,0,0,0],
     [0,0,0,1,0],
     [1,1,0,1,1],
     [0,0,0,0,0]],
    [0,4],
    [3,2]
) == False

# Example 3, unreachable stopping point
assert solution.hasPath(
    [[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]
) == False

# Simple direct path
assert solution.hasPath(
    [[0,0],
     [0,0]],
    [0,0],
    [0,1]
) == True

# Destination passed through but not stoppable
assert solution.hasPath(
    [[0,0,0]],
    [0,0],
    [0,1]
) == False

# Maze with cycles
assert solution.hasPath(
    [[0,0,0],
     [0,1,0],
     [0,0,0]],
    [0,0],
    [2,2]
) == True

# Single corridor
assert solution.hasPath(
    [[0,0,0,0,0]],
    [0,0],
    [0,4]
) == True

# Blocked destination
assert solution.hasPath(
    [[0,1,0],
     [0,1,0],
     [0,0,0]],
    [0,0],
    [0,2]
) == False

print("All tests passed.")
Test Why
Example 1 Valid reachable stopping path
Example 2 Destination can be crossed but not stopped on
Example 3 Unreachable stopping position
Simple direct path Basic movement correctness
Pass-through destination Verifies stopping logic
Maze with cycles Ensures visited tracking works
Single corridor Tests long rolling behavior
Blocked destination Tests disconnected regions

Edge Cases

Destination is passed through but cannot be stopped on

One of the trickiest aspects of this problem is that the ball may roll through the destination without stopping there.

For example:

[0,0,0]

Starting from the leftmost cell and rolling right causes the ball to stop only at the far-right wall boundary. The middle cell is crossed but never becomes a stopping point.

A naive implementation that checks whether the ball ever touches the destination during rolling would incorrectly return True.

This implementation only checks positions after rolling completely stops, which correctly handles this case.

Cycles in the maze

A maze may allow the ball to revisit the same stopping positions repeatedly.

Without a visited set, DFS or BFS could loop forever.

For example:

0 0 0
0 1 0
0 0 0

The ball can repeatedly cycle around the central wall.

The implementation prevents infinite traversal by marking each stopping position visited immediately after discovery.

Long uninterrupted corridors

A maze may contain long rows or columns with no internal walls.

In these cases, the rolling simulation must continue correctly until the final stopping point.

A common bug is stopping one step too early or overshooting the wall boundary.

This implementation avoids those mistakes by checking whether the next cell is valid before advancing:

while next_position_is_valid:
    move_forward

As a result, the ball always stops at the correct final empty cell before the wall.