MediumArrayDepth-First SearchBreadth-First SearchMatrix

Maze

1 approach, code in every language

A ball is placed in a maze represented by an m x n grid. Each cell is either empty, written as 0, or a wall, written as 1.

The ball can roll up, down, left, or right, but once it starts rolling in a direction it does not stop until it strikes a wall. Only after stopping can it choose a new direction.

Given the ball's start position and a destination position (each given as [row, column]), determine whether the ball can come to rest exactly at the destination. Return true if it can, and false otherwise. You may assume the borders of the maze are all walls, and that the start and destination are distinct empty cells.

Example 1

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

One route is down, then left, then down; the ball comes to rest exactly on the destination.

Example 2

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

The ball can never stop at [3, 2]; whenever it rolls through that cell it keeps going until a wall stops it elsewhere.

Constraints

m == maze.length
n == maze[i].length
1 <= m, n <= 100
maze[i][j] is 0 or 1
start.length == 2 and destination.length == 2
0 <= startRow, destinationRow < m
0 <= startCol, destinationCol < n
Both the ball and the destination sit on empty cells, and they are different
The maze contains at least two empty cells

Breadth-First Search over Stopping Positions

BFS over the positions where the ball can stop; from each stop, roll in all four directions until a wall blocks it, and treat each resulting stop as a neighbor.

Loading animation…

Intuition

Even though the ball moves cell by cell, the only positions that matter for decisions are the places where it can actually stop, which are next to walls. We therefore build a graph whose nodes are stopping positions and run breadth-first search over them. From a given stop, rolling in one of the four directions until a wall blocks the way produces exactly one neighboring stop. We mark stops as visited so the search does not loop, and we succeed the moment the destination appears as a stop. If the queue empties without landing on the destination, the ball can never rest there.

Algorithm walkthrough

1Create a visited matrix, enqueue the start position, and mark it visited.
2Pop a stopping position; if it equals the destination, return true.
3For each of the four directions, roll from the current stop, advancing while the next cell is in-bounds and open.
4The cell where the roll halts is a neighboring stop; if it has not been visited, mark it and enqueue it.
5Continue until the queue empties; if the destination was never dequeued, return false.

Implementation

from collections import deque

class Solution:
    def hasPath(self, maze: list[list[int]], start: list[int], destination: list[int]) -> bool:
        m, n = len(maze), len(maze[0])
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        visited = [[False] * n for _ in range(m)]
        queue = deque([(start[0], start[1])])
        visited[start[0]][start[1]] = True
        while queue:
            row, col = queue.popleft()
            if row == destination[0] and col == destination[1]:
                return True
            for dr, dc in directions:
                nr, nc = row, col
                while 0 <= nr + dr < m and 0 <= nc + dc < n and maze[nr + dr][nc + dc] == 0:
                    nr += dr
                    nc += dc
                if not visited[nr][nc]:
                    visited[nr][nc] = True
                    queue.append((nr, nc))
        return False

Time

O(m * n * (m + n))

Space

O(m * n)

There are up to m * n stopping cells, and from each one a single roll can traverse an entire row or column, costing O(m + n). The visited matrix and queue use O(m * n) space.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free