The Maze - Practice Coding Problems

The Maze - Problem

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 to roll. Given the m x n maze, the ball's start position and the destination, where start = [startrow, startcol] and destination = [destinationrow, destinationcol], return true if the ball can stop at the destination, otherwise return false.

You may assume that the borders of the maze are all walls.

Input & Output

Example 1 — Path Exists

$ 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

💡 Note: Ball starts at (0,4), rolls down to (4,4), then rolls right to reach destination (4,4)

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: false

💡 Note: Ball cannot stop at (3,2) because it's blocked by walls and there's no path that allows stopping there

Example 3 — Start Equals Destination

$ 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 = [0,0], destination = [0,0]

› Output: true

💡 Note: Ball is already at destination, so return true immediately

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 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

Visualization

Tap to expand

Understanding the Visualization

Input

5x5 maze with start [0,4] and destination [4,4]

Process

Ball rolls in directions until hitting walls

Output

Return true if ball can stop at destination

Key Takeaway

🎯 Key Insight: The ball only stops when hitting a wall, making this a graph traversal problem between stopping positions

Asked in

G Google 42 f Facebook 38 a Amazon 35 M Microsoft 28

The key insight is that the ball only stops when it hits a wall, not at every cell. Best approach is DFS with visited tracking to avoid revisiting positions. Time: O(m×n), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS	O(4^(m×n))	O(m×n)	Try every possible direction from each stopping position without optimization
DFS with Visited Set	O(m×n)	O(m×n)	Use DFS with visited tracking to avoid revisiting positions
BFS with Queue	O(m×n)	O(m×n)	Use breadth-first search to explore all reachable positions level by level

Brute Force DFS — Algorithm Steps

Start from initial position
Roll in each direction until hitting wall
Recursively explore from each stopping position
Check if any path reaches destination

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Begin at starting position [0,4]

Roll & Explore

Roll in each direction until hitting wall, then recurse

Check Result

Return true if any path reaches destination

Code -

solution.c — C

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

bool dfs(int maze[][5], int rows, int cols, int x, int y, int destX, int destY) {
    if (x == destX && y == destY) {
        return true;
    }
    
    int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    for (int i = 0; i < 4; i++) {
        int nx = x, ny = y;
        int dx = directions[i][0], dy = directions[i][1];
        
        // Roll until hitting wall
        while (nx + dx >= 0 && nx + dx < rows && 
               ny + dy >= 0 && ny + dy < cols && 
               maze[nx + dx][ny + dy] == 0) {
            nx += dx;
            ny += dy;
        }
        
        // If stopped at different position, continue exploring
        if (nx != x || ny != y) {
            if (dfs(maze, rows, cols, nx, ny, destX, destY)) {
                return true;
            }
        }
    }
    return false;
}

bool solution(int maze[][5], int rows, int cols, int startX, int startY, int destX, int destY) {
    return dfs(maze, rows, cols, startX, startY, destX, destY);
}

int main() {
    int maze[5][5] = {{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}};
    int start[2] = {0, 4};
    int dest[2] = {4, 4};
    
    bool result = solution(maze, 5, 5, start[0], start[1], dest[0], dest[1]);
    printf(result ? "true\n" : "false\n");
    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 can go as deep as number of cells in maze

⚡ Linearithmic Space

89.2K Views

Medium Frequency

~25 min Avg. Time

1.5K 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

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler