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

0% completed

Vote For New Content
The Maze II (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>], find the shortest distance for the ball to reach the destination. If the ball can't reach the destination, return -1.

The distance is the number of empty spaces traveled by the ball from the start (excluded) to the destination (included).

Examples

Example 1

  • Input: start = [0, 1], 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: 7
Image
  • Justification: The ball travels from the start (0,1) down to (2,1), right to (2, 2), down to (4, 2), and right to (4, 4) in 7 moves.

Example 2

  • Input: start = [0, 0], destination = [4, 4], maze = 
    [[0, 0, 0, 0, 0],
 [1, 1, 1, 1, 0],
 [0, 0, 0, 0, 0],
 [0, 1, 1, 1, 0],
 [0, 0, 0, 0, 0]]
  • Expected Output: 8
Image
  • Justification: The ball travels from (0,0) right to (0,4), down to (4,4) in 8 moves.

Example 3

  • Input: start = [0, 1], destination = [3, 1], maze = 
    [[0, 0, 1, 0, 0],
 [0, 1, 1, 0, 0],
 [0, 1, 0, 0, 1],
 [1, 0, 0, 1, 0],
 [0, 0, 0, 0, 0]]
  • Expected Output: -1
  • Justification: The ball cannot reach the destination (3,1) due to walls blocking the path.

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