Shortest Path to Get All Keys

Hard

#0818Time: Exponential. The exact complexity is difficult to pin down but is much worse than the optimal solution. It explores a large number of paths in the state graph, many of which are redundant. This will lead to a 'Time Limit Exceeded' verdict.Space: O(m * n * 2^k) in the worst case for the recursion stack depth, where `m` and `n` are grid dimensions and `k` is the number of keys.3 companies

Patterns

Bit Manipulation

Algorithms

Breadth-First Search

Data structures

Array Matrix

Companies

Airbnb Pinterest Roku

Prompt

You are given an m x n grid grid where:

'.' is an empty cell.
'#' is a wall.
'@' is the starting point.
Lowercase letters represent keys.
Uppercase letters represent locks.

You start at the starting point and one move consists of walking one space in one of the four cardinal directions. You cannot walk outside the grid, or walk into a wall.

If you walk over a key, you can pick it up and you cannot walk over a lock unless you have its corresponding key.

For some 1 <= k <= 6, there is exactly one lowercase and one uppercase letter of the first k letters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.

Return the lowest number of moves to acquire all keys. If it is impossible, return -1.

Example 1:

Input: grid = ["@.a..","###.#","b.A.B"]
Output: 8
Explanation: Note that the goal is to obtain all the keys not to open all the locks.

Example 2:

Input: grid = ["@..aA","..B#.","....b"]
Output: 6

Example 3:

Input: grid = ["@Aa"]
Output: -1

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 30
grid[i][j] is either an English letter, '.', '#', or '@'.
There is exactly one '@' in the grid.
The number of keys in the grid is in the range [1, 6].
Each key in the grid is unique.
Each key in the grid has a matching lock.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach attempts to solve the problem by exploring every possible path from the start point using a Depth-First Search (DFS). It recursively explores adjacent cells, keeping track of the current position, the keys collected (via a bitmask), and the number of steps taken. A global minimum is updated whenever a path that collects all keys is found. However, without memoization (dynamic programming), this method is a brute-force exploration of the state space and is very inefficient.

Algorithm

Define a recursive function, say dfs(row, col, mask, steps).
Use a global variable min_steps initialized to infinity to store the length of the shortest path found so far.
The state of the recursion is defined by the current position (row, col) and the bitmask mask of collected keys.
To avoid infinite loops, use a visited set that stores the tuple (row, col, mask) for the current path. This is crucial; a simple visited[row][col] is not enough as a cell might be revisited with a different set of keys.
The base case for the recursion is when all keys are collected (i.e., mask equals the target mask). At this point, update min_steps with the current number of steps.
Another base case is for pruning: if steps already exceeds min_steps, terminate that path.
In the recursive step, explore all four cardinal directions.
For each valid neighbor:
- If it's a key, update the mask.
- If it's a lock, check if the corresponding key is in the current mask.
- If the move is permissible, make a recursive call with the updated state and steps + 1.
This method exhaustively searches all possible paths, which is highly inefficient due to re-computation of paths to the same state.

Walkthrough

The brute-force DFS algorithm works by trying to find all paths that collect all keys and then picking the shortest one. A recursive function, let's call it dfs(row, col, mask, steps), is the core of this approach.

State Representation: The state is defined by (row, col, mask), where (row, col) is the current position and mask is a bitmask representing the keys collected.
Recursion: Starting from the '@' position with a mask of 0 and 0 steps, the function explores all four neighbors.
Path Exploration: For each valid move (within bounds, not a wall), it checks the cell type:
- Empty ('.') or Start ('@'): Move to the new cell with the same mask.
- Key ('a'-'f'): Move to the new cell and update the mask by setting the corresponding bit.
- Lock ('A'-'F'): Check if the current mask has the required key. If yes, move to the new cell; otherwise, this path is blocked.
Termination: When a state is reached where all keys are collected, the current number of steps is compared with a global minimum, and the minimum is updated if the current path is shorter.
Cycle Prevention: To avoid getting stuck in loops, a visited set must be used. Critically, this set must store the entire state (row, col, mask) to distinguish between visiting the same cell with different sets of keys. This visited set should track visited states for the current recursive path only and backtrack (remove the state) when returning from a recursive call.

This approach is fundamentally flawed for efficiency because it doesn't recognize that the shortest path to a state (row, col, mask) is unique. It will repeatedly calculate the path to the same state via different routes, leading to an exponential number of computations.

Complexity

Time

Exponential. The exact complexity is difficult to pin down but is much worse than the optimal solution. It explores a large number of paths in the state graph, many of which are redundant. This will lead to a 'Time Limit Exceeded' verdict.

Space

O(m * n * 2^k) in the worst case for the recursion stack depth, where `m` and `n` are grid dimensions and `k` is the number of keys.

Trade-offs

Pros

Conceptually simple if one is familiar with recursion and backtracking.

Cons

Extremely inefficient and will likely time out for most test cases.
It re-explores paths to the same state (row, col, mask) multiple times.
The complexity of managing the visited state for path-specific tracking can be tricky to implement correctly.

The most efficient way to solve this problem is to view it as a shortest path problem on a state graph. A state is defined not just by the position (row, col) but also by the set of keys collected. Since every move has a cost of 1, Breadth-First Search (BFS) is the ideal algorithm. It systematically explores the graph level by level, guaranteeing that the first time we reach a state where all keys are collected, it will be via the shortest possible path.

Algorithm

First, parse the grid to find the starting coordinates (startX, startY) and the total number of keys keyCount.
The state of our search will be (row, col, mask), where mask is a bitmask representing the keys collected.
Initialize a queue for BFS and add the starting state (startX, startY, 0).
Create a 3D boolean array visited[m][n][1 << keyCount] to keep track of visited states and prevent cycles. Mark the initial state as visited.
The target state is any state where the mask equals (1 << keyCount) - 1.
Perform a level-order traversal (standard BFS):
- Initialize steps = 0.
- While the queue is not empty, process all nodes at the current level.
- For each state (r, c, mask) dequeued:
  - If mask is the target mask, we have found the shortest path. Return steps.
  - Explore the four neighbors (nr, nc).
  - For each valid neighbor (not a wall, within bounds):
    - Handle the cell type:
      - Key: Calculate newMask = mask | (1 << (key - 'a')).
      - Lock: Check if mask has the corresponding key. If not, this move is invalid.
      - Empty: The mask remains unchanged.
    - If the resulting new state (nr, nc, newMask) has not been visited, add it to the queue and mark it as visited.
- After processing a full level, increment steps.
If the queue becomes empty and the target mask was never reached, it's impossible to collect all keys. Return -1.

Walkthrough

This approach models the problem as a shortest path search on an unweighted graph where nodes are states. A state is a tuple (row, col, mask).

State Definition: (row, col) represents the current coordinates, and mask is an integer bitmask where the i-th bit is 1 if we have the i-th key ('a' + i) and 0 otherwise.
Initialization: We find the start position '@' and count the total number of keys, k. The goal is to reach any state with a mask of (1 << k) - 1.
BFS Setup: We use a queue to store states to visit and a 3D visited array, visited[row][col][mask], to avoid redundant computations and infinite loops. The BFS begins by enqueuing the initial state (start_row, start_col, 0).
Traversal: The BFS proceeds level by level. In each level, we dequeue all states currently in the queue and generate their successor states. For a state (r, c, mask), we check its four neighbors:
- If a neighbor (nr, nc) is a wall (#), it's ignored.
- If it's a lock ('A'-'F'), we check if we have the key using the bitmask: (mask & (1 << (lock - 'A'))) != 0. If we don't have the key, the move is invalid.
- If it's a key ('a'-'f'), we calculate a newMask by setting the corresponding bit: newMask = mask | (1 << (key - 'a')).
- For any valid move that leads to a new state (nr, nc, newMask) that has not been visited, we mark it as visited and add it to the queue.
Goal: The first time we generate a state where the mask equals the target mask, we have found the shortest path. The length of this path is the current level of the BFS. If the queue becomes empty before we find such a state, it means collecting all keys is impossible.

1import java.util.LinkedList;2import java.util.Queue;3 4class Solution {5    public int shortestPathAllKeys(String[] grid) {6        int m = grid.length;7        int n = grid[0].length();8        int startX = -1, startY = -1;9        int keyCount = 0;10 11        for (int i = 0; i < m; i++) {12            for (int j = 0; j < n; j++) {13                char c = grid[i].charAt(j);14                if (c == '@') {15                    startX = i;16                    startY = j;17                } else if (c >= 'a' && c <= 'f') {18                    keyCount++;19                }20            }21        }22 23        // State: [row, col, mask]24        Queue<int[]> queue = new LinkedList<>();25        // Visited: visited[row][col][mask]26        boolean[][][] visited = new boolean[m][n][1 << keyCount];27 28        // Initial state29        queue.offer(new int[]{startX, startY, 0});30        visited[startX][startY][0] = true;31 32        int steps = 0;33        int targetMask = (1 << keyCount) - 1;34        int[] dr = {-1, 1, 0, 0};35        int[] dc = {0, 0, -1, 1};36 37        while (!queue.isEmpty()) {38            int size = queue.size();39            for (int i = 0; i < size; i++) {40                int[] current = queue.poll();41                int r = current[0];42                int c = current[1];43                int mask = current[2];44 45                if (mask == targetMask) {46                    return steps;47                }48 49                for (int j = 0; j < 4; j++) {50                    int nr = r + dr[j];51                    int nc = c + dc[j];52 53                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr].charAt(nc) != '#') {54                        char cell = grid[nr].charAt(nc);55                        int newMask = mask;56 57                        if (cell >= 'a' && cell <= 'f') {58                            // It's a key59                            newMask |= (1 << (cell - 'a'));60                        } else if (cell >= 'A' && cell <= 'F') {61                            // It's a lock62                            if ((mask & (1 << (cell - 'A'))) == 0) {63                                // Don't have the key, cannot pass64                                continue;65                            }66                        }67                        68                        // If this state has not been visited, add to queue69                        if (!visited[nr][nc][newMask]) {70                            visited[nr][nc][newMask] = true;71                            queue.offer(new int[]{nr, nc, newMask});72                        }73                    }74                }75            }76            steps++;77        }78 79        return -1;80    }81}

Complexity

Time

O(m * n * 2^k). Each state `(row, col, mask)` is visited at most once. From each state, we explore 4 neighbors in constant time.

Space

O(m * n * 2^k), where `m` and `n` are the grid dimensions and `k` is the number of keys. This space is used for the `visited` array and the queue.

Trade-offs

Pros

Guaranteed to find the shortest path because BFS explores level by level.
Efficient and optimal for the given problem constraints.
Avoids re-computing paths to the same state (row, col, mask) by using a visited array.

Cons

The space complexity can be high if the grid dimensions or the number of keys were significantly larger.

Solutions

Solution

1class Solution {2private3  int[] dirs = {-1, 0, 1, 0, -1};4public5  int shortestPathAllKeys(String[] grid) {6    int m = grid.length, n = grid[0].length();7    int k = 0;8    int si = 0, sj = 0;9    for (int i = 0; i < m; ++i) {10      for (int j = 0; j < n; ++j) {11        char c = grid[i].charAt(j);12        if (Character.isLowerCase(c)) {13          ++k;14        } else if (c == '@') {15          si = i;16          sj = j;17        }18      }19    }20    Deque<int[]> q = new ArrayDeque<>();21    q.offer(new int[]{si, sj, 0});22    boolean[][][] vis = new boolean[m][n][1 << k];23    vis[si][sj][0] = true;24    int ans = 0;25    while (!q.isEmpty()) {26      for (int t = q.size(); t > 0; --t) {27        var p = q.poll();28        int i = p[0], j = p[1], state = p[2];29        if (state == (1 << k) - 1) {30          return ans;31        }32        for (int h = 0; h < 4; ++h) {33          int x = i + dirs[h], y = j + dirs[h + 1];34          if (x >= 0 && x < m && y >= 0 && y < n) {35            char c = grid[x].charAt(y);36            if (c == '#' ||37                (Character.isUpperCase(c) && ((state >> (c - 'A')) & 1) == 0)) {38              continue;39            }40            int nxt = state;41            if (Character.isLowerCase(c)) {42              nxt |= 1 << (c - 'a');43            }44            if (!vis[x][y][nxt]) {45              vis[x][y][nxt] = true;46              q.offer(new int[]{x, y, nxt});47            }48          }49        }50      }51      ++ans;52    }53    return -1;54  }55}

1class Solution {2public:3  const static inline vector<int> dirs = {-1, 0, 1, 0, -1};4  int shortestPathAllKeys(vector<string> &grid) {5    int m = grid.size(), n = grid[0].size();6    int k = 0;7    int si = 0, sj = 0;8    for (int i = 0; i < m; ++i) {9      for (int j = 0; j < n; ++j) {10        char c = grid[i][j];11        if (islower(c))12          ++k;13        else if (c == '@')14          si = i, sj = j;15      }16    }17    queue<tuple<int, int, int>> q{{{si, sj, 0}}};18    vector<vector<vector<bool>>> vis(19        m, vector<vector<bool>>(n, vector<bool>(1 << k)));20    vis[si][sj][0] = true;21    int ans = 0;22    while (!q.empty()) {23      for (int t = q.size(); t; --t) {24        auto [i, j, state] = q.front();25        q.pop();26        if (state == (1 << k) - 1)27          return ans;28        for (int h = 0; h < 4; ++h) {29          int x = i + dirs[h], y = j + dirs[h + 1];30          if (x >= 0 && x < m && y >= 0 && y < n) {31            char c = grid[x][y];32            if (c == '#' || (isupper(c) && (state >> (c - 'A') & 1) == 0))33              continue;34            int nxt = state;35            if (islower(c))36              nxt |= 1 << (c - 'a');37            if (!vis[x][y][nxt]) {38              vis[x][y][nxt] = true;39              q.push({x, y, nxt});40            }41          }42        }43      }44      ++ans;45    }46    return -1;47  }48};

1class Solution:2    def shortestPathAllKeys(self, grid: List[str]) -> int: m, n = len(grid), len(grid[0]) si, sj = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == '@') k = sum(v . islower() for row in grid for v in row) dirs = (- 1, 0, 1, 0, - 1) q = deque([(si, sj, 0)]) vis = {(si, sj, 0)} ans = 0 while q: for _ in range(len(q)): i, j, state = q . popleft() if state == (1 << k) - 1: return ans for a, b in pairwise(dirs): x, y = i + a, j + b nxt = state if 0 <= x < m and 0 <= y < n: c = grid[x][y] if (c == '#' or c . isupper() and (state & (1 << (ord(c) - ord('A')))) == 0): continue if c . islower(): nxt |= 1 << (ord(c) - ord('a')) if (x, y, nxt) not in vis: vis . add((x, y, nxt)) q . append((x, y, nxt)) ans += 1 return - 1

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem