LeetCode 490: The Maze Solution in Python – A Step-by-Step Guide

What Is LeetCode 490: The Maze?

In LeetCode 490: The Maze, you’re given a 2D grid maze (0s for open spaces, 1s for walls), a start position start [row, col], and a destination destination [row, col]. A ball starts at start and can roll in four directions (up, down, left, right), stopping only when it hits a wall (1). Your task is to determine if the ball can reach destination by rolling any sequence of moves. For example, in 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], the ball can roll right then down to reach [4,4], returning True. It’s like guiding a marble through a labyrinth, letting it bounce off walls to find the exit.

Problem Statement

• Input:
• maze (List[List[int]])—2D grid of 0s (open) and 1s (walls).
• start (List[int])—[row, col] starting position.
• destination (List[int])—[row, col] target position.
• Output: bool—True if ball can reach destination, False otherwise.
• Rules:
• Ball rolls until hitting a wall (1) or edge.
• Can roll up, down, left, right from each stop.
• Start and destination are open cells (0).

Constraints

• \( 1 \leq m, n \leq 100 \) (maze dimensions).
• maze[i][j] is 0 or 1.
• start and destination are valid, distinct positions.

Examples to Get Us Started

• Input: 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]
• Output: True (Roll right to [0,4], down to [4,4]).
• Input: 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 = [3,2]
• Output: False (No path to [3,2]).
• Input: maze = [[0]], start = [0,0], destination = [0,0]
• Output: True (Already at destination).

Understanding the Problem: Rolling to Victory

To solve LeetCode 490: The Maze in Python, we need to determine if a ball can roll from start to destination in a maze, where it moves in one direction until hitting a wall or edge, then chooses a new direction. A naive approach—simulating every roll sequence—could be inefficient for a 100x100 grid with many paths. The key? Use BFS to explore all reachable stop points (where the ball hits a wall) efficiently, simulating rolling in O(n) time per move. We’ll explore:

• Best Solution (BFS with Rolling Simulation): O(m * n) time, O(m * n) space—fast and optimal (m, n = maze dimensions).
• Alternative Solution (DFS with Exhaustive Path Exploration): O(4^(m * n)) time, O(m * n) space—simple but slow.

Let’s dive into the BFS solution—it’s the maze runner’s swift compass we need.

Best Solution: BFS with Rolling Simulation

Why This Is the Best Solution

The BFS with rolling simulation is the top pick because it’s O(m * n) time and O(m * n) space, efficiently finding if the ball can reach the destination by exploring all possible stop points (where it hits a wall) level-by-level, using a queue to ensure the shortest path is checked first. It simulates rolling in each direction until a wall, tracking visited stops to avoid cycles. It’s like rolling the ball systematically, marking each wall-hit spot and checking the goal—smart and optimal!

How It Works

Here’s the strategy:

• Step 1: Define rolling function:
• Roll from (x, y) in direction (dx, dy) until wall or edge, return stop point.
• Step 2: BFS setup:
• Queue with (start_x, start_y), visited set for stop points.
• Step 3: BFS loop:
• Dequeue current (x, y).
• Roll in 4 directions, enqueue new stop points if unvisited.
• If stop = destination, return True.
• Step 4: Return False if queue exhausted.
• Why It Works:
• BFS ensures shortest path, but here checks reachability.
• Rolling simulation captures maze mechanics.

Step-by-Step Example

Example: 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], dest = [4,4]

• Init: Queue = [(0,4)], visited = {(0,4)}.
• (0,4):
• Up: Hits [0,4] (edge), skip (visited).
• Right: Hits [0,4] (edge), skip.
• Down: Rolls to [4,4] (hits [4,3]=1), queue = [(4,4)], visited = {(0,4), (4,4)}.
• Left: Hits [0,2]=1, stop at [0,3], queue = [(4,4), (0,3)].
• (4,4): Matches dest, return True.
• Result: True.

Example: maze = [[0,0,1],[0,1,0],[0,0,0]], start = [0,0], dest = [2,2]

• (0,0): Down → [2,0], Right → [0,1], queue = [(2,0), (0,1)].
• (2,0): Right → [2,2], queue = [(0,1), (2,2)].
• (2,2): Matches dest, True.
• Result: True.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codefrom collections import deque

class Solution:
    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
        # Directions: up, right, down, left
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        m, n = len(maze), len(maze[0])

        # Step 1: Rolling simulation function
        def roll(x: int, y: int, dx: int, dy: int) -> tuple:
            while 0 <= x + dx < m and 0 <= y + dy < n and maze[x + dx][y + dy] == 0:
                x += dx
                y += dy
            return x, y

        # Step 2: BFS setup
        queue = deque([(start[0], start[1])])
        visited = {(start[0], start[1])}

        # Step 3: BFS loop
        while queue:
            x, y = queue.popleft()
            if [x, y] == destination:
                return True

            # Roll in all 4 directions
            for dx, dy in directions:
                next_x, next_y = roll(x, y, dx, dy)
                if (next_x, next_y) not in visited:
                    visited.add((next_x, next_y))
                    queue.append((next_x, next_y))

        # Step 4: No path found
        return False

• Line 6-7: Define directions and grid size.
• Line 9-13: roll: Simulate rolling until wall/edge, return stop.
• Line 16-18: BFS: Start queue with (start), visited set.
• Line 21-30: BFS:
• Dequeue current position.
• If destination, return True.
• Roll in 4 directions, enqueue unvisited stops.
• Line 33: Return False if queue empty.
• Time Complexity: O(m * n)—each cell visited once, rolling O(m+n).
• Space Complexity: O(m * n)—queue and visited set.

It’s like a maze-rolling navigator!

Alternative Solution: DFS with Exhaustive Path Exploration

Why an Alternative Approach?

The DFS with exhaustive path exploration—O(4^(m * n)) time, O(m * n) space—recursively tries all possible rolling sequences from the start, checking if any reach the destination, without pruning or queue optimization. It’s slow but intuitive, like rolling the ball everywhere to see if it lands at the goal. Good for small mazes or learning!

How It Works

• Step 1: DFS with visited set:
• Roll in each direction, recurse if unvisited.
• Step 2: Base: if current = dest, return True.
• Step 3: Return False if all paths explored.
• Step 4: Start DFS from start.

Step-by-Step Example

Example: maze = [[0,0],[0,0]]

• (0,0): Down → (1,0), Right → (0,1).
• (1,0): Right → (1,1).
• (1,1): Up → (0,1), Left → (1,0), covered all.
• Result: True if dest in path.

Code for DFS (Simplified)

Copy codeclass Solution:
    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        m, n = len(maze), len(maze[0])
        visited = set()

        def roll(x: int, y: int, dx: int, dy: int) -> tuple:
            while 0 <= x + dx < m and 0 <= y + dy < n and maze[x + dx][y + dy] == 0:
                x += dx
                y += dy
            return x, y

        def dfs(x: int, y: int) -> bool:
            if (x, y) in visited:
                return False
            if [x, y] == destination:
                return True
            visited.add((x, y))
            for dx, dy in directions:
                next_x, next_y = roll(x, y, dx, dy)
                if dfs(next_x, next_y):
                    return True
            return False

        return dfs(start[0], start[1])

• Line 6-19: Roll and DFS:
• Roll to stop, recurse if unvisited.
• Time Complexity: O(4^(m * n))—exponential paths.
• Space Complexity: O(m * n)—visited set.

It’s a slow maze wanderer!

Comparing the Two Solutions

• BFS (Best):
• Pros: O(m * n), fast, optimal.
• Cons: O(m * n) space.
• DFS (Alternative):
• Pros: O(4^(m * n)), simple.
• Cons: Impractical for large grids.

BFS wins for efficiency.

Edge Cases and Examples

• Single cell: Start = dest → True.
• All walls: No path → False.
• Open grid: Reachable → True.

BFS handles all perfectly.

Complexity Recap

• BFS: Time O(m * n), Space O(m * n).
• DFS: Time O(4^(m * n)), Space O(m * n).

BFS is the champ.

Key Takeaways

• BFS: Roll level-by-level.
• DFS: Explore all paths.
• Python Tip: BFS finds fast—see [Python Basics](/python/basics).

Final Thoughts: Roll to Victory

LeetCode 490: The Maze in Python is a rolling maze adventure. BFS with rolling simulation is your swift compass, while DFS is a slow trek. Want more maze fun? Try LeetCode 489: Robot Room Cleaner or LeetCode 505: The Maze II. Ready to roll some balls? Head to Solve LeetCode 490 on LeetCode and navigate it today—your coding skills are maze-ready!