Practice/Meta/Leetcode 490. The Maze

Leetcode 490. The Maze

CodingMust

Problem

You are given a rectangular maze represented as a 2D grid where:

• 0 represents an empty space
• 1 represents a wall

A ball starts at a given position and can roll in four directions: up, down, left, or right. The key mechanic is that once the ball starts rolling in a direction, it cannot stop until it hits a wall or the maze boundary. The ball will stop in the empty cell just before the wall.

Your task is to determine whether the ball can reach a specific destination position and stop exactly there.

Requirements

1. Return true if the ball can reach and stop at the destination, false otherwise
2. The ball must stop exactly at the destination (not just pass through it)
3. The ball continues rolling in a direction until hitting a wall or boundary
4. The ball can change direction only when it stops

Constraints

• 1 <= maze.length, maze[0].length <= 100
• maze[i][j] is 0 or 1
• start and destination are guaranteed to be empty cells (value 0)
• There is at most one path from start to any stopping position
• Time complexity target: O(m × n) where m and n are maze dimensions
• Space complexity target: O(m × n) for the visited set

Examples

Example 1:

` 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

Explanation: The ball starts at (0,4) and can roll down. It stops at (4,4) which is the destination. `

Example 2:

` 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

Explanation: The ball can reach (3,2) but cannot stop there. When rolling toward (3,2), it would continue past that position. `

Example 3:

` Input: maze = [[0,0,0], [0,1,0], [0,0,0]] start = [1,0] destination = [1,0]

Output: true

Explanation: The ball is already at the destination. `