We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

The Maze

Number: 490

Difficulty: Medium

Paid? Yes

Companies: Meta, Walmart Labs, Amazon, Nvidia, Uber, Block, Pinterest, TikTok, Google

Problem Description

There is a ball in a maze represented by a 2D grid where empty spaces are marked as 0 and walls as 1. The ball can roll continuously in one of the four cardinal directions (up, down, left, right) until it meets a wall, and then it can choose a new direction. Given the maze, a starting position, and a destination position, determine if the ball can stop exactly at the destination.

Key Insights

  • The ball continues moving in one direction until it hits a wall (or the boundary, which is considered a wall).
  • You must simulate the ball's rolling rather than taking a single step.
  • Even if the ball passes through the destination, it is only valid if it can stop exactly there.
  • A breadth-first search (BFS) or depth-first search (DFS) strategy is ideal because we need to explore all stopping positions.
  • Use a visited structure to avoid revisiting positions and thus prevent infinite loops.

Space and Time Complexity

Time Complexity: O(m * n) where m and n are the dimensions of the maze. Space Complexity: O(m * n) due to the storage used by the visited matrix and the BFS/DFS queue or recursion stack.

Solution

We simulate the ball's movement using a breadth-first search (BFS) approach. Each time we pick a stop position, we try to roll in all four directions until the ball hits a wall. At that point, if the new stopping position has not been visited, we mark it as visited and add it to our queue. If we ever reach the destination exactly, we return true. The key is simulating the "roll" by iteratively moving in a direction until no further move is possible.

We store the coordinates in a queue (or stack for DFS) along with a 2D visited array to monitor which positions have been processed. The directions are maintained in a list/array, and for each direction, we keep moving until the next cell would be out of bounds or a wall.

Code Solutions

# Function to determine if there is a valid path in the maze from start to destination
def hasPath(maze, start, destination):
    from collections import deque
    rows, cols = len(maze), len(maze[0])
    # Create a visited 2D array to keep track of processed cells
    visited = [[False] * cols for _ in range(rows)]
    queue = deque([tuple(start)])
    visited[start[0]][start[1]] = True

    # Directions: up, down, left, right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # Process nodes in BFS fashion
    while queue:
        current = queue.popleft()
        # Check if the current position is the destination
        if [current[0], current[1]] == destination:
            return True
        # Explore all four possible directions
        for dx, dy in directions:
            x, y = current
            # Roll the ball until it hits a wall or boundary
            while 0 <= x + dx < rows and 0 <= y + dy < cols and maze[x + dx][y + dy] == 0:
                x += dx
                y += dy
            # If this new stop has not been visited, add it to the queue
            if not visited[x][y]:
                visited[x][y] = True
                queue.append((x, y))
    return False

# Example usage:
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]
print(hasPath(maze, start, destination))  # Expected output: True
← Back to All Questions