The Maze
Problem Statement
A ball sits in a maze. The maze is a grid where 0 is an empty cell and 1 is a wall. The ball can only move by rolling. When you push it in one direction (up, down, left or right), it rolls over empty cells and keeps going until the next cell is a wall or the edge of the maze. Then it stops on the last empty cell it reached.
The ball can roll over the destination without stopping there. Return true if the ball can stop on the destination, starting from the start cell. Otherwise return false.
maze, a grid of 0s and 1s. start, the [row, column] where the ball starts. destination, the [row, column] of the target. Rows and columns start at 0.
true if the ball can stop on the destination, otherwise false.
Roll down from (0,0): the wall under (2,0) stops the ball at (2,0). Roll right: the wall at (2,3) stops it at (2,2). Roll down: the ball reaches the bottom row and stops at (4,2).
Rolling down column 4 passes over (3,4), but the ball only stops at the bottom edge, (4,4). No roll ends on (3,4).
Roll down to (2,0), roll right to (2,2), then roll up. The ball passes (1,2) and stops at the top edge, (0,2).
- • The maze has at least one row and one column.
- • Every cell is either 0 (empty) or 1 (wall).
- • The start and the destination are cells inside the maze, given as [row, column].
Pattern Recognition Clues
Recognising these key signals in the problem description immediately identifies the pattern:
Approach Complexity Ladder
Try every roll path that never repeats a resting cell on the same path, and check whether one rests on the destination
BFS over resting cells only; each one is queued once, and the destination counts only when the ball rests on it
From the start, roll in each direction to a resting cell, then recurse from there. The search remembers only the resting cells on the current path, so a path never loops. When a path ends, the search forgets it, so the same resting cells are walked again through other paths. Return true when a path rests on the destination.
Recognition rule for this sub-pattern:
Unlock Complete Visual Walkthrough & Optimal C++
The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.
How this concept connects to System Design & C++ Systems
Top engineering interviews test whether you understand how algorithms like Graph BFS / DFS translate into production architectures and low-level memory mechanics.