The Maze II - Practice Coding Problems

The Maze II - Problem

Array Depth-First Search Breadth-First Search Graph Heap (Priority Queue) Matrix Shortest Path Medium

There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the m x n maze, the ball's start position and the destination, where start = [startrow, startcol] and destination = [destinationrow, destinationcol], return the shortest distance for the ball to stop at the destination. If the ball cannot stop at destination, return -1.

The distance is the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included). You may assume that the borders of the maze are all walls.

Input & Output

Example 1 — Basic Path

$ 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: 12

💡 Note: Ball starts at (0,4), rolls left to (0,0), then down to (4,0), then right to (4,4). Total distance: 4 + 4 + 4 = 12 steps

Example 2 — No Path

$ 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: -1

💡 Note: There is no way for the ball to stop at destination (3,2) because it's surrounded by walls and unreachable

Example 3 — Direct Path

$ Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]

› Output: 6

💡 Note: Ball rolls up from (4,3) to (0,3), then left to (0,1). Distance: 4 + 2 = 6 steps

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_row, destination_row < m
0 ≤ start_col, destination_col < n
Both start and destination exist in an empty space

Visualization

Tap to expand

Understanding the Visualization

Input

Ball at start position, destination marked, walls block movement

Rolling

Ball rolls in direction until hitting wall, then can choose new direction

Shortest Path

Find minimum number of steps to reach destination

Key Takeaway

🎯 Key Insight: Model the problem as shortest path in a graph where nodes are stopping positions after rolling until hitting walls

Asked in

G Google 45 f Facebook 38 a Amazon 32 M Microsoft 28

The key insight is that the ball rolls until it hits a wall, making each stopping position a node in a graph. The optimal approach uses Dijkstra's algorithm with a priority queue to efficiently find the shortest path. Time: O(m×n×log(m×n)), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ DFS with All Paths	O(4^(m×n))	O(m×n)	Use DFS to explore all possible paths and track minimum distance
BFS Level-by-Level	O(m×n×max(m,n))	O(m×n)	Use BFS to explore positions level by level, guaranteeing shortest path
Dijkstra with Priority Queue	O(m×n×log(m×n))	O(m×n)	Use Dijkstra's algorithm with min-heap to find shortest path efficiently

DFS with All Paths — Algorithm Steps

Start DFS from initial position
For each direction, roll until hitting wall
If reached destination, update minimum distance
Continue exploring from new positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Begin DFS from starting position

Roll & Explore

Roll in each direction until hitting wall

Track Minimum

Keep track of shortest distance to destination

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int minDist;
int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

void dfs(int** maze, int m, int n, int x, int y, int* destination, int dist) {
    if (x == destination[0] && y == destination[1]) {
        if (dist < minDist) {
            minDist = dist;
        }
        return;
    }
    
    if (dist >= minDist) return;
    
    for (int i = 0; i < 4; i++) {
        int nx = x, ny = y, steps = 0;
        while (nx + directions[i][0] >= 0 && nx + directions[i][0] < m && 
               ny + directions[i][1] >= 0 && ny + directions[i][1] < n && 
               maze[nx + directions[i][0]][ny + directions[i][1]] == 0) {
            nx += directions[i][0];
            ny += directions[i][1];
            steps++;
        }
        
        if (steps > 0) {
            dfs(maze, m, n, nx, ny, destination, dist + steps);
        }
    }
}

int solution(int** maze, int m, int n, int* start, int* destination) {
    minDist = INT_MAX;
    dfs(maze, m, n, start[0], start[1], destination, 0);
    return minDist == INT_MAX ? -1 : minDist;
}

int main() {
    // Simple implementation assuming proper input format
    // Parse maze, start, destination
    // Call solution and print result
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4^(m×n))

In worst case, explores 4 directions from each of m×n positions recursively

✓ Linear Growth

Space Complexity

O(m×n)

Recursion stack depth can be up to m×n in worst case

⚡ Linearithmic Space

142.0K Views

Medium Frequency

~25 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with All Paths — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler