LeetCode 505: The Maze II Solution in Python – A Step-by-Step Guide

What Is LeetCode 505: The Maze II?

In LeetCode 505: The Maze II, you’re given a 2D maze grid (0s for empty spaces, 1s for walls), a start position, and a destination. A ball rolls in one direction (up, down, left, right) until it hits a wall, and you need to find the shortest distance (number of steps) to reach the destination—or return -1 if impossible. Unlike typical maze problems, the ball doesn’t stop at each cell; it rolls until obstructed. For example, in a 5x5 maze, rolling from (0,4) to (4,4) might take 12 steps. This builds on LeetCode 490: The Maze, adding distance tracking.

Problem Statement

• Input:
• maze: 2D list of 0s (empty) and 1s (walls).
• start: [row, col] starting position.
• destination: [row, col] target position.
• Output: Integer—shortest distance to destination, or -1 if unreachable.
• Rules: Ball rolls until hitting a wall; distance is total steps rolled.

Constraints

• Maze size: 1 ≤ rows, cols ≤ 100.
• start and destination are within bounds, not walls.
• At least one empty cell exists.

Examples

• 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
• Roll down to (4,4) via stops.
• 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
• No path exists.
• Input: maze = [[0,0],[0,0]], start = [0,0], destination = [1,1]
• Output: 2
• Down, then right.

Understanding the Problem: Rolling Through the Maze

To solve LeetCode 505: The Maze II in Python, we need a method to simulate the ball’s rolling, track distances, and find the shortest path in a maze where movement isn’t cell-by-cell but wall-to-wall. A naive approach might try all paths, but with a 100x100 grid, we need efficiency. We’ll use:

• Best Solution (Dijkstra’s with Priority Queue): O(mn log mn) time, O(mn) space—optimal for shortest path.
• Alternative Solution (BFS with Distance): O(mn) time, O(mn) space—simpler but explores more.

Let’s dive into Dijkstra’s with a friendly breakdown!

Best Solution: Dijkstra’s Algorithm with Priority Queue

Why Dijkstra’s Is the Best

Dijkstra’s algorithm with a priority queue is the top pick for LeetCode 505 because it guarantees the shortest path in a weighted graph (here, weights are roll distances). Using a min-heap, it’s O(mn log mn) time (m, n are maze dimensions) and O(mn) space—perfect for efficiently exploring stops. It’s like having a GPS that always picks the quickest route through the maze!

How It Works

Think of this as a rolling roadmap:

• Step 1: Setup:
• Use a priority queue (min-heap) with (distance, row, col).
• Track shortest distance to each cell in a distances array.
• Step 2: Roll in Four Directions:
• From each stop, roll up, down, left, right until hitting a wall.
• Calculate distance rolled.
• Step 3: Explore Greedily:
• Pop smallest distance from heap.
• If shorter than known distance to that stop, update and push neighbors.
• Step 4: Check Destination:
• Return distance to destination or -1 if unreachable.
• Why It Works:
• Priority queue ensures we process shortest paths first.
• Rolling simulates problem rules.

It’s like rolling with a smart compass!

Step-by-Step Example

Example: 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]

• Init:
• Heap: [(0, 0, 4)].
• distances = { (0,4): 0 }.
• Step 1: Pop (0, 0, 4):
• Roll up: Hit (-1,4), stop at (0,4).
• Roll down: Hit (5,4), stop at (4,4), dist = 4.
• distances[(4,4)] = 4, push (4, 4, 4).
• Roll left: Hit (0,2), stop at (0,2), dist = 2.
• distances[(0,2)] = 2, push (2, 0, 2).
• Roll right: Hit (0,5), stop at (0,4).
• Step 2: Pop (2, 0, 2):
• Roll down: Stop at (2,2), dist = 2 + 2 = 4.
• distances[(2,2)] = 4, push (4, 2, 2).
• Roll left: Stop at (0,0), dist = 2.
• distances[(0,0)] = 2, push (2, 0, 0).
• Step 3: Pop (2, 0, 0):
• Roll down: Stop at (4,0), dist = 4.
• distances[(4,0)] = 6, push (6, 4, 0).
• Step 4: Pop (4, 2, 2):
• Roll right: Stop at (2,4), dist = 2.
• distances[(2,4)] = 6, push (6, 2, 4).
• Step 5: Pop (4, 4, 4):
• Destination reached, check distances[(4,4)] = 4.
• Continue: Explore others, but 4 is shortest to (4,4).
• Result: 12 (after further optimization, see full path).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeimport heapq

class Solution:
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        m, n = len(maze), len(maze[0])
        start, dest = tuple(start), tuple(destination)

        # Step 1: Setup priority queue and distances
        pq = [(0, start[0], start[1])]  # (distance, row, col)
        distances = {start: 0}          # Shortest distance to each point

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

        # Step 2: Dijkstra’s algorithm
        while pq:
            dist, r, c = heapq.heappop(pq)

            # If reached destination
            if (r, c) == dest:
                return dist

            # If this path isn’t shortest, skip
            if dist > distances[(r, c)]:
                continue

            # Step 3: Roll in all directions
            for dr, dc in directions:
                new_r, new_c = r, c
                steps = 0

                # Roll until hitting a wall
                while 0 <= new_r + dr < m and 0 <= new_c + dc < n and maze[new_r + dr][new_c + dc] == 0:
                    new_r += dr
                    new_c += dc
                    steps += 1

                new_dist = dist + steps
                new_pos = (new_r, new_c)

                # If shorter path found
                if new_pos not in distances or new_dist < distances[new_pos]:
                    distances[new_pos] = new_dist
                    heapq.heappush(pq, (new_dist, new_r, new_c))

        return -1  # Unreachable

• Lines 6-7: Convert inputs to tuples for hashing.
• Lines 10-11: Min-heap with initial state; distances dict.
• Line 14: Four rolling directions.
• Lines 17-20: Pop shortest distance; return if destination.
• Line 23: Skip if not shortest path to this stop.
• Lines 26-36: Roll in each direction until wall, count steps.
• Lines 39-42: If new shorter path, update and push to heap.
• Time Complexity: O(mn log mn)—heap ops for mn cells.
• Space Complexity: O(mn)—heap and distances.

It’s like a rolling pathfinder!

Alternative Solution: BFS with Distance Tracking

Why an Alternative Approach?

BFS with distance tracking explores all stops level-by-level, tracking distances. It’s O(mn) time and O(mn) space—simpler to grasp but less efficient than Dijkstra’s since it doesn’t prioritize shortest paths. Great for understanding maze traversal basics.

How It Works

Picture this as a rolling wave:

• Step 1: Queue with (row, col, distance).
• Step 2: Roll in four directions from each stop.
• Step 3: Track visited stops and distances.
• Step 4: Return shortest to destination or -1.

It’s like flooding the maze with rolls!

Step-by-Step Example

Example: maze = [[0,0],[0,0]], start = [0,0], destination = [1,1]

• Init: Queue: [(0,0,0)], distances = {(0,0): 0}.
• Step 1: Dequeue (0,0,0):
• Down: (1,0), dist = 1, queue += (1,0,1).
• Right: (0,1), dist = 1, queue += (0,1,1).
• Step 2: Dequeue (1,0,1):
• Right: (1,1), dist = 2, queue += (1,1,2).
• Step 3: Dequeue (0,1,1):
• Down: (1,1), dist = 2 (already 2).
• Step 4: Dequeue (1,1,2):
• Destination, return 2.
• Result: 2.

Code for BFS

Copy codefrom collections import deque

class Solution:
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        m, n = len(maze), len(maze[0])
        start, dest = tuple(start), tuple(destination)

        queue = deque([(start[0], start[1], 0)])  # (row, col, distance)
        distances = {start: 0}

        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

        while queue:
            r, c, dist = queue.popleft()

            if (r, c) == dest:
                return dist

            for dr, dc in directions:
                new_r, new_c = r, c
                steps = 0

                while 0 <= new_r + dr < m and 0 <= new_c + dc < n and maze[new_r + dr][new_c + dc] == 0:
                    new_r += dr
                    new_c += dc
                    steps += 1

                new_dist = dist + steps
                new_pos = (new_r, new_c)

                if new_pos not in distances or new_dist < distances[new_pos]:
                    distances[new_pos] = new_dist
                    queue.append((new_r, new_c, new_dist))

        return -1

• Time Complexity: O(mn)—visits each cell once.
• Space Complexity: O(mn)—queue and distances.

It’s a rolling flood!

Comparing the Two Solutions

• Dijkstra’s (Best):
• Pros: O(mn log mn), optimal shortest path.
• Cons: Heap logic.
• BFS (Alternative):
• Pros: O(mn), simpler.
• Cons: Explores more than needed.

Dijkstra’s wins for efficiency!

Additional Examples and Edge Cases

• [[0]], [0,0], [0,0]: 0—start = dest.
• [[0,1],[1,0]], [0,0], [1,1]: -1—blocked.
• [[0,0,0],[0,1,0],[0,0,0]], [0,0], [2,2]: 4.

Dijkstra’s handles them all!

Complexity Recap

• Dijkstra’s: Time O(mn log mn), Space O(mn).
• BFS: Time O(mn), Space O(mn).

Dijkstra’s is the shortest-path king!

Key Takeaways

• Dijkstra’s: Priority = shortest—learn at Python Basics!
• BFS: Simple exploration.
• Rolling: Unique maze twist.
• Fun: Navigate like a pro!

Final Thoughts: Roll to the Goal!

LeetCode 505: The Maze II in Python is a thrilling maze challenge. Dijkstra’s with a priority queue nails the shortest path, while BFS keeps it basic. Want more? Try LeetCode 490: The Maze or LeetCode 743: Network Delay Time. Ready to roll? Head to Solve LeetCode 505 on LeetCode and find that shortest distance today!