Shortest Path to Get All Keys

Shortest Path to Get All Keys

What is this problem about?

The Shortest Path to Get All Keys interview question gives you a grid containing open cells (.), walls (#), a start position (@), keys (lowercase letters a-f), and locks (corresponding uppercase letters A-F). Find the minimum number of steps to collect all keys. You can pass through a lock only if you have the corresponding key. This combines BFS with bitmask state tracking for key collection.

Why is this asked in interviews?

Meta, Airbnb, Google, and Adobe ask this HARD problem because it demonstrates BFS with exponential state space compression via bitmasks. The state must include both position AND the set of currently held keys — without bitmask encoding, tracking which keys are held would be intractable. It models resource-collecting path planning in game AI, dungeon navigation, and multi-step workflow automation.

Algorithmic pattern used

The pattern is BFS with state (row, col, key_bitmask). Initialize BFS from the start cell @ with key_mask = 0. For each state, try all 4 neighbors: skip walls; skip locks if the corresponding key bit isn't set. When stepping on a key cell, add the key bit to the mask in the new state. Track visited states as (row, col, mask). Return the step count when the mask equals (1 << num_keys) - 1 (all keys collected).

Example explanation

Grid:

@ . a
. # B
b . .

Keys: a, b. Locks: B. Target mask = 0b11 = 3.

BFS:

• Start (0,0, mask=0).
• Reach (0,2): pick up key 'a'. State: (0,2, mask=01).
• Reach (2,0): pick up key 'b'. State: (2,0, mask=11).
• All keys collected → return step count.

Common mistakes candidates make

• Not including the key_mask in the visited state — revisiting a cell with different keys collected must be allowed.
• Attempting to pass through a lock without the corresponding key — always check bit lock_index in the current mask.
• Not updating the mask immediately upon reaching a key cell — the new mask must be used in the next BFS expansion.
• Using (1 << 26) - 1 for the target mask — only num_keys bits are needed, not all 26.

Interview preparation tip

For the Shortest Path to Get All Keys coding problem, the BFS bitmask graph interview pattern is the key skill. The state tuple (row, col, key_mask) is the critical insight — it augments standard BFS with key collection history. Meta and Pinterest interviewers test the bitmask setup: key_mask |= (1 << (ord(cell) - ord('a'))) to add a key. Practice this bitmask-BFS pattern — it appears in "collect all items" grid problems, Hamiltonian path approximations, and level design validation in game development interviews.