The Maze

MediumGraphsbfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A ball sits in a grid maze where 0 is an open cell and 1 is a wall. The ball can be pushed up, down, left, or right, but once pushed it keeps rolling until the next cell in that direction is a wall or outside the grid; only then does it stop and can be pushed again. Given the maze, the ball's start cell [row, col], and a destination cell, return true if the ball can come to rest exactly on destination. Rolling through the destination without stopping there does not count. If start equals destination, the ball is already at rest there, so return true. Both start and destination are open cells. The area outside the grid acts as a wall.

Examples

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
Left stops at (0,3), down at (1,3), left at (1,0), down at (2,0), right at (2,2), down at (4,2), and right at (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
The ball can pass through (3,2) going up or down, but nothing ever stops it there.

Constraints

  • `1 <= m, n <= 100`
  • `maze[i][j]` is `0` or `1`
  • `start` and `destination` are open cells inside the grid

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bfs problems