Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
The Maze (medium)
On this page

Problem Statement

Examples

Try it yourself

Problem Statement

There is a ball in a maze with empty spaces (0) and walls (1). The ball can move up, down, left, or right through empty spaces but won't stop until it hits a wall. When the ball stops, it can change direction.

Given an m x n maze, the ball's start position, and the destination, where start = [start<sub>row</sub>, start<sub>col</sub>] and destination = [destination<sub>row</sub>, destination<sub>col</sub>], return true if the ball can stop at the destination. If the ball can't stop at the destination, return false.

Examples

Example 1:

  • Input: start = [0, 4], destination = [0, 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]]
  • Expected Output: true
Image
  • Justification: One possible way to stop at the destination is:- left -> down -> left -> up -> right.

Example 2:

  • Input: start = [0, 3], destination = [4, 4], 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]]
  • Expected Output: true
Image
  • Justification: One possible way to stop at the destination is:- down -> left -> down -> right -> down -> right.

Example 3:

  • Input: start = [0, 3], destination = [1, 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]]
  • Expected Output: false
Image
  • Justification: The ball cannot stop at (1, 1) because it is not hitting the walls.

Constraints:

  • m == maze.length
  • n == maze[i].length
  • 1 <= m, n <= 100
  • maze[i][j] is 0 or 1.
  • start.length == 2
  • destination.length == 2
  • 0 <= start<sub>row</sub>, destination<sub>row</sub> < m
  • 0 <= start<sub>col</sub>, destination<sub>col</sub> < n
  • Both the ball and the destination exist in an empty space, and they will not be in the same position initially.
  • The maze contains at least 2 empty spaces.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

On this page

Problem Statement

Examples

Try it yourself