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 II

Number: 505

Difficulty: Medium

Paid? Yes

Companies: TikTok, Meta, Amazon, Google

Problem Description

Given a maze represented as a 2D grid where 0 denotes an empty space and 1 denotes a wall, a ball starts at the given start position and must roll to a destination position. The ball moves continuously in one of the four directions (up, down, left, right) until it hits a wall. It can only change direction when it stops. The goal is to find the shortest distance (i.e., the number of empty spaces traversed, counting the destination but not the starting cell) for the ball to stop exactly at the destination. If no such path exists, return -1.

Key Insights

  • The ball rolls until it hits a wall, so each move is not one step but a continuous travel in a direction.
  • The problem can be modeled as finding the shortest path in a weighted graph where nodes are positions in the maze and edge weights are the distance traveled in that roll.
  • A priority queue (min-heap) based algorithm, such as Dijkstra’s algorithm, is ideal since each roll covers variable distances.
  • Always check if the new computed distance for a cell is less than a previously recorded one before pushing it to the heap.

Space and Time Complexity

Time Complexity: O(m * n * log(m * n)), where m and n are the maze dimensions (each cell may get processed and queued with a logarithmic cost). Space Complexity: O(m * n) for maintaining the distance matrix and the priority queue.

Solution

We solve the problem using a modified version of Dijkstra’s algorithm. The maze grid is treated as a graph where each cell is a node and an edge exists between the current cell and the cell where the ball stops after rolling in one direction. For every cell popped from the priority queue, we roll the ball in all four directions until it hits a wall, counting the number of steps taken. If the distance calculated from this roll is shorter than a previously stored distance for the stopping cell, we update the distance and add it to the priority queue. This process continues until we either reach the destination (and return the distance) or exhaust all possibilities (returning -1).

Code Solutions

import heapq

def shortestDistance(maze, start, destination):
    m, n = len(maze), len(maze[0])
    # Initialize distance matrix with infinity
    dist = [[float('inf')] * n for _ in range(m)]
    dist[start[0]][start[1]] = 0
    # Priority queue (min-heap) storing tuples (distance, row, col)
    heap = [(0, start[0], start[1])]
    # Directions: up, down, left, right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while heap:
        d, row, col = heapq.heappop(heap)
        # If we have reached the destination, return the corresponding distance
        if [row, col] == destination:
            return d
        # Skip if we already found a better path to (row, col)
        if d > dist[row][col]:
            continue
        for dr, dc in directions:
            next_row, next_col, count = row, col, 0
            # Roll the ball until it hits a wall
            while 0 <= next_row + dr < m and 0 <= next_col + dc < n and maze[next_row + dr][next_col + dc] == 0:
                next_row += dr
                next_col += dc
                count += 1
            # Check if the new distance is shorter
            if d + count < dist[next_row][next_col]:
                dist[next_row][next_col] = d + count
                heapq.heappush(heap, (dist[next_row][next_col], next_row, next_col))
    return -1
← Back to All Questions