Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

864. Shortest Path to Get All Keys - Leetcode Solution

Code Implementation

from collections import deque

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m, n = len(grid), len(grid[0])
        key_count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '@':
                    start = (i, j)
                if 'a' <= grid[i][j] <= 'f':
                    key_count += 1

        queue = deque()
        visited = set()
        queue.append((start[0], start[1], 0, 0))  # row, col, keys_bitmask, steps
        visited.add((start[0], start[1], 0))
        target = (1 << key_count) - 1

        while queue:
            x, y, keys, steps = queue.popleft()
            for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
                nx, ny = x + dx, y + dy
                if not (0 <= nx < m and 0 <= ny < n):
                    continue
                cell = grid[nx][ny]
                if cell == '#':
                    continue
                new_keys = keys
                if 'a' <= cell <= 'f':
                    new_keys = keys | (1 << (ord(cell) - ord('a')))
                    if new_keys == target:
                        return steps + 1
                if 'A' <= cell <= 'F':
                    if not (keys & (1 << (ord(cell.lower()) - ord('a')))):
                        continue
                if (nx, ny, new_keys) not in visited:
                    visited.add((nx, ny, new_keys))
                    queue.append((nx, ny, new_keys, steps + 1))
        return -1
      
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int shortestPathAllKeys(vector<string>& grid) {
        int m = grid.size(), n = grid[0].size();
        int key_count = 0, sx, sy;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '@') { sx = i; sy = j; }
                if (grid[i][j] >= 'a' && grid[i][j] <= 'f') key_count++;
            }
        }
        int target = (1 << key_count) - 1;
        queue<tuple<int,int,int,int>> q;
        set<tuple<int,int,int>> visited;
        q.emplace(sx, sy, 0, 0); // x, y, keys, steps
        visited.emplace(sx, sy, 0);
        vector<pair<int,int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.empty()) {
            auto [x, y, keys, steps] = q.front(); q.pop();
            for (auto& d : dirs) {
                int nx = x + d.first, ny = y + d.second;
                if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
                char c = grid[nx][ny];
                if (c == '#') continue;
                int new_keys = keys;
                if (c >= 'a' && c <= 'f') {
                    new_keys |= (1 << (c - 'a'));
                    if (new_keys == target) return steps + 1;
                }
                if (c >= 'A' && c <= 'F') {
                    if (!(keys & (1 << (c - 'A')))) continue;
                }
                if (!visited.count({nx, ny, new_keys})) {
                    visited.emplace(nx, ny, new_keys);
                    q.emplace(nx, ny, new_keys, steps + 1);
                }
            }
        }
        return -1;
    }
};
      
import java.util.*;

class Solution {
    public int shortestPathAllKeys(String[] grid) {
        int m = grid.length, n = grid[0].length();
        int keyCount = 0, sx = 0, sy = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char c = grid[i].charAt(j);
                if (c == '@') { sx = i; sy = j; }
                if ('a' <= c && c <= 'f') keyCount++;
            }
        }
        int target = (1 << keyCount) - 1;
        Queue<int[]> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        q.offer(new int[]{sx, sy, 0, 0}); // x, y, keys, steps
        visited.add(sx + "," + sy + ",0");
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int x = curr[0], y = curr[1], keys = curr[2], steps = curr[3];
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
                char cell = grid[nx].charAt(ny);
                if (cell == '#') continue;
                int nkeys = keys;
                if ('a' <= cell && cell <= 'f') {
                    nkeys = keys | (1 << (cell - 'a'));
                    if (nkeys == target) return steps + 1;
                }
                if ('A' <= cell && cell <= 'F') {
                    if ((keys & (1 << (cell - 'A'))) == 0) continue;
                }
                String state = nx + "," + ny + "," + nkeys;
                if (!visited.contains(state)) {
                    visited.add(state);
                    q.offer(new int[]{nx, ny, nkeys, steps + 1});
                }
            }
        }
        return -1;
    }
}
      
/**
 * @param {string[]} grid
 * @return {number}
 */
var shortestPathAllKeys = function(grid) {
    const m = grid.length, n = grid[0].length;
    let keyCount = 0, sx, sy;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid[i][j] === '@') { sx = i; sy = j; }
            if (grid[i][j] >= 'a' && grid[i][j] <= 'f') keyCount++;
        }
    }
    const target = (1 << keyCount) - 1;
    const queue = [[sx, sy, 0, 0]]; // x, y, keys, steps
    const visited = new Set();
    visited.add(`${sx},${sy},0`);
    const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
    while (queue.length) {
        const [x, y, keys, steps] = queue.shift();
        for (const [dx, dy] of dirs) {
            const nx = x + dx, ny = y + dy;
            if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
            const cell = grid[nx][ny];
            if (cell === '#') continue;
            let nkeys = keys;
            if (cell >= 'a' && cell <= 'f') {
                nkeys = keys | (1 << (cell.charCodeAt(0) - 'a'.charCodeAt(0)));
                if (nkeys === target) return steps + 1;
            }
            if (cell >= 'A' && cell <= 'F') {
                if (!(keys & (1 << (cell.charCodeAt(0) - 'A'.charCodeAt(0))))) continue;
            }
            const state = `${nx},${ny},${nkeys}`;
            if (!visited.has(state)) {
                visited.add(state);
                queue.push([nx, ny, nkeys, steps + 1]);
            }
        }
    }
    return -1;
};

Problem Description

You are given a 2D grid representing a maze. The grid contains:

  • @: Your starting position (only one in the grid)
  • .: An empty cell you can walk through
  • #: A wall you cannot pass
  • a to f: Keys you can collect (up to 6 different keys)
  • A to F: Locks that can only be opened with the corresponding key
Your goal is to find the minimum number of steps required to collect all the keys. You can move up, down, left, or right, but cannot move through walls. You can only pass through a lock if you have already collected its corresponding key. Each key can be collected only once. If it is impossible to collect all keys, return -1.

Thought Process

When first approaching this problem, it might seem similar to a shortest path problem in a maze. However, the twist is that the state of the player depends not just on their position, but also on which keys they have collected. A brute-force approach would try all possible paths, but this quickly becomes infeasible as the number of keys increases, due to the exponential number of possible states.

To optimize, we realize that the problem can be modeled as a stateful search, where each state is a combination of the player's current position and the set of keys collected so far. We want to find the shortest sequence of moves that results in collecting all keys. Since we want the shortest path, Breadth-First Search (BFS) is a natural fit, but we must extend the state to include the keys collected.

To avoid revisiting the same state, we need to track not just positions we've visited, but the specific set of keys we had at that position. This prevents cycles and redundant work.

Solution Approach

Here is a step-by-step breakdown of the optimized approach:

  1. Identify the Start and Keys: Scan the grid to find the starting position and count how many keys there are. Each key is represented by a lowercase letter from a to f.
  2. State Representation: For BFS, each state consists of:
    • Current coordinates (x, y)
    • A bitmask representing which keys have been collected (since there are at most 6 keys, we can use an integer where each bit represents a key)
    • The number of steps taken so far (for BFS level tracking)
  3. Visited Set: To avoid cycles, maintain a set of visited states, where each state is uniquely identified by (x, y, keys_bitmask).
  4. BFS Traversal: Use a queue to perform BFS. At each step:
    • For each of the four directions, compute the next position.
    • If the next cell is a wall (#), skip it.
    • If it's a key, update the bitmask to reflect that the key has been collected.
    • If it's a lock, check if the corresponding key has been collected. If not, skip this move.
    • If the new state has not been visited, add it to the queue and mark it as visited.
    • If all keys have been collected (i.e., the bitmask has all key bits set), return the number of steps taken.
  5. Termination: If the queue is exhausted without collecting all keys, return -1.
We use a bitmask for keys because it allows for fast O(1) operations to add/check keys, and it keeps the state compact for visited tracking.

Example Walkthrough

Let's consider the following grid: 

    ["@.a..",
     "###.#",
     "b.A.B"]
  • Start at (0,0) (@)
  • There are two keys: a at (0,2) and b at (2,0)
  • There are two locks: A at (2,2) and B at (2,4)
Step-by-step:
  1. From (0,0), move right to (0,1), then right to (0,2) to collect key a (bitmask now 01).
  2. Now, move down to (1,2) (it's a wall, so not possible). Instead, backtrack and go down to (1,0) (blocked by wall), so try another path.
  3. From (0,2), back to (0,1), then to (1,1) (blocked), so try moving to (0,3), then (0,4), down to (1,4) (blocked), so that's not possible.
  4. Instead, from (0,2), try going back to (0,1), then to (1,1) (blocked), so try from start to (2,0) to collect b (bitmask now 11).
  5. Once both keys are collected, BFS finds the shortest path that collects both, considering the locks can only be opened after collecting the corresponding keys.
The minimum number of steps to collect both keys is 8.

Time and Space Complexity

Brute-force approach: Would be exponential, as it would try all possible permutations of paths and key pickups, leading to O((m*n)*(2^K)*K!), where K is the number of keys. This is not feasible for K up to 6.

Optimized BFS approach:

  • There are at most m*n positions and 2^K key combinations (since each key can be either collected or not).
  • The total number of unique states is O(m*n*2^K).
  • Each state is processed at most once, and each move takes O(1) time, so the total time complexity is O(m*n*2^K).
  • Space complexity is also O(m*n*2^K) for the queue and visited set.
This is efficient enough for the problem's constraints (m, n ≤ 30, K ≤ 6).

Summary

The problem is a classic example of a shortest path search with extra state (the set of collected keys). By modeling the state as (position, keys_bitmask) and using BFS, we ensure we find the shortest path efficiently. The use of a bitmask for keys is both elegant and efficient, and tracking visited states in this way prevents unnecessary recomputation. This makes the solution both optimal and easy to reason about, leveraging classic BFS with a twist for stateful traversal.