Abstract / Summary

Find the shortest path to collect all keys in a grid with obstacles and locked doors.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 55% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Bit Manipulation
• Breadth First Search
• Matrix

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic “shortest path to collect all keys” problem on a rectangular grid. It treats the grid as a maze containing walls (#), empty cells (.), a start position (@), keys (a-z) and locks (A-Z). The algorithm explores reachable states with a priority queue, tracks collected keys using a bitmask, and terminates as soon as every key has been gathered. The design emphasizes compact state representation and aggressive pruning of already-seen configurations.

Core Functions

Adding a key to the current mask

The helper addKey receives the current bitmask and a character from the grid. It ignores non-key symbols, skips locks, and for a lowercase key computes its bit position (ord(key) - ord('a')). The mask is updated with a bitwise OR.

def addKey(keys, newKey):
    if newKey in [".", "#", "@"]:
        return keys
    if "A" <= newKey <= "Z":    # skip locks
        return keys
    id = ord(newKey) - ord("a") # keys are lowercase
    return keys | (1 << id)

Checking whether a lock can be opened

hasKey determines if the current key set permits entry into a cell. Empty cells and keys are always traversable. For a lock, the corresponding bit is examined; the function returns True only when the required key bit is present.

def hasKey(keys, lock):
    # always allowed to go to empty cells or cells with a key
    if lock in [".", "@"] or "a" <= lock <= "z":
        return True
    id = ord(lock) - ord("A") # locks are uppercase
    return (keys & (1 << id)) != 0

Initialization

The algorithm first computes the dimensions of the grid, then scans every cell to locate the start position and to build the allKeys mask that represents the set of all keys present in the maze. The start state is inserted into the priority queue (todo) with zero steps and an empty key mask.

allKeys = 0
width   = len(grid[0])
height  = len(grid)
todo = []  # steps, x, y, keys
for y in range(height):
    for x in range(width):
        if grid[y][x] == "@":
            todo.append((0, 0, x, y))
        # pick up any key
        allKeys = addKey(allKeys, grid[y][x])

Main Search Loop

The loop repeatedly extracts the state with the smallest step count from the heap. Each extracted tuple contains the number of steps taken so far, the current key mask, and the coordinates.

while todo:
    steps, keys, x, y = heappop(todo)

Loop-avoidance and state pruning

A seen set stores triples (keys, x, y). Before expanding a state, the algorithm checks whether this exact configuration has already been processed. If it has, the iteration is skipped.

To further reduce redundancy, the code also records all subsets of the current key mask for the same cell. By iterating through the bits of keys and clearing the least-significant set bit in each step, every smaller mask is added to seen. This ensures that later arrivals with fewer keys to the same location are recognized as already explored, preventing unnecessary re-expansion.

lookup = (keys, x, y)
if lookup in seen:
    continue
seen.add(lookup)
# (speed up)
lesskeys = keys
while lesskeys != 0:
    lesskeys &= lesskeys - 1
    seen.add((lesskeys, x, y))

Validating movement through locks

Before any key acquisition, the algorithm verifies that the current cell is accessible with the existing key set. If a lock blocks the cell and the required key is missing, the state is discarded.

if not hasKey(keys, grid[y][x]):
    continue

Updating the key mask

If the cell contains a key, addKey merges it into the current mask. When the updated mask equals allKeys, the function returns the number of steps taken, because the shortest path to collect every key has been found.

keys = addKey(keys, grid[y][x])
if keys == allKeys:
    return steps

Enqueuing neighboring cells

The algorithm examines the four orthogonal neighbors, skips walls, and pushes each viable neighbor onto the heap with an incremented step count while preserving the current key mask.

if x > 0 and grid[y][x - 1] != "#":
    todo.append((steps + 1, keys, x - 1, y))
if x < width - 1 and grid[y][x + 1] != "#":
    todo.append((steps + 1, keys, x + 1, y))
if y > 0 and grid[y - 1][x] != "#":
    todo.append((steps + 1, keys, x, y - 1))
if y < height - 1 and grid[y + 1][x] != "#":
    todo.append((steps + 1, keys, x, y + 1))

If the heap empties without reaching a state where all keys are collected, the function returns -1, indicating that the maze configuration makes it impossible to gather every key.

return -1

Edge Cases Handled

The code gracefully manages several special situations:

• Multiple keys of the same type - Adding a key that is already present leaves the mask unchanged, thanks to the idempotent bitwise OR operation.
• Locks without corresponding keys - hasKey returns False for a lock when the required bit is absent, preventing entry into locked cells.
• Start cell adjacent to a wall - Neighbor checks explicitly verify that a target cell is not a wall before enqueuing, so the algorithm never attempts to move through #.
• Empty grid or missing start - The initialization loop only inserts a start state when @ is found; if absent, the heap remains empty and the function returns -1.
• All keys already present at the start - The initial mask is empty, but allKeys may be zero if no keys exist. The first extraction from the heap will satisfy keys == allKeys, causing an immediate return of 0.
• Large numbers of keys - The bitmask representation scales up to 26 keys (the alphabet size) without needing additional data structures, and the subset-pruning loop efficiently iterates over set bits only.

Performance Optimizations

The implementation incorporates several techniques that reduce the search space and improve runtime:

• Bitmask for key tracking - Representing the set of collected keys as a 32-bit integer enables constant-time checks and updates, avoiding costly container operations.
• Priority queue (heap) for BFS - By always expanding the state with the fewest steps, the algorithm behaves like Dijkstra’s search on an unweighted graph, guaranteeing that the first time a full-key mask is reached corresponds to the shortest path.
• State pruning with subsets - After visiting a cell with a particular key set, the code records all subsets of that mask as already seen for the same coordinates. This prevents later expansions that would carry fewer keys to the same location, a common source of exponential blow-up in key-collection problems.
• Early exit on completion - As soon as the mask matches allKeys, the function returns, avoiding further exploration of longer paths.
• Avoiding redundant wall checks - Neighbor generation checks the wall condition once per direction, ensuring that only viable moves are pushed onto the heap.

These strategies together keep the number of explored states manageable even for dense mazes with many keys and locks.

Imagine a maze filled with walls, magical doors, and colorful keys. The goal is to walk around and collect every single key so you can unlock the doors that are blocking your path.

First, the computer looks at every square in the maze. It counts how many keys are hidden there and finds the starting spot marked with a special symbol. It keeps a tiny list of where it has been so it does not walk in circles.

The computer uses a little helper to remember which keys are in its pocket. When it walks onto a square, it checks if that square is a wall. If it is a wall, it stays put. If it is a key, it puts the key in its pocket. If it is a locked door, it checks its pocket to see if it has the matching color key to open it.

The computer is very smart because it explores all the paths at the same time, always picking the shortest way to reach a new spot. It keeps walking, picking up keys, and opening doors until it has gathered every single key hidden in the maze. Once the pocket is full of all the necessary treasures, it knows the journey is done.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: exponential
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++			Python	Java			TS
	WalkCCC	C++				Java
	leetcode.ca	C++			Python	Java	Go
	LeetcodeHelp	C++			Python	Java
	Progiez	C++			Python	Java
github	black-shadows	C++
	charles-wangkai					Java
	everthis		JS
	halfrost						Go
	JoshCrozier		JS
	lkwq007				Python
	ruoru			Rust
	suxrobGM							C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
ruoru	Rust
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality