Watch 10 video solutions for Shortest Path to Get All Keys, a hard level problem involving Array, Bit Manipulation, Breadth-First Search. This walkthrough by Aryan Mittal has 8,819 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an m x n grid grid where:
'.' is an empty cell.'#' is a wall.'@' is the starting point.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.lengthn == grid[i].length1 <= m, n <= 30grid[i][j] is either an English letter, '.', '#', or '@'. '@' in the grid.[1, 6].Problem Overview: You are given a grid representing a maze with walls, keys, and locks. Starting from @, move in four directions and collect all keys while only passing through locks if you already hold the matching key. The goal is to return the minimum number of steps required to collect every key.
Approach 1: Breadth-First Search (BFS) with State Tracking (O(m*n*2^k) time, O(m*n*2^k) space)
This problem is fundamentally a shortest path search on a grid, which makes Breadth-First Search the natural starting point. The tricky part is that the player's state depends not only on the current cell but also on which keys have been collected. Encode the keys using a bitmask (for example, bit i represents key 'a'+i). Each BFS state becomes (row, col, keyMask). When you move onto a key cell, update the mask using bit manipulation. A visited set must track all three components to avoid revisiting the same location with the same key set. The search stops once the mask equals the target mask containing all keys.
Approach 2: A* Search Algorithm (O(m*n*2^k) worst case, typically faster in practice; O(m*n*2^k) space)
A* search improves exploration efficiency by prioritizing promising states. Instead of a plain queue, use a priority queue ordered by f(n) = g(n) + h(n), where g(n) is the distance traveled and h(n) estimates the remaining distance to collect keys. A simple heuristic is the Manhattan distance to the nearest remaining key in the matrix. The state representation remains (row, col, keyMask). The heuristic guides the search toward key locations earlier, reducing unnecessary exploration compared with standard BFS on larger grids.
Approach 3: Bidirectional Search (BFS) (O(m*n*2^k) time, O(m*n*2^k) space)
Bidirectional BFS attempts to reduce search depth by exploring from both ends simultaneously. One frontier expands from the starting position while another represents states where all keys are collected. Each state still tracks (row, col, keyMask). When the frontiers intersect, the shortest path is found. The complexity remains similar to standard BFS, but in practice it can shrink the search space when the grid is large and the number of keys is small.
Recommended for interviews: BFS with state tracking is the expected solution. It clearly models the grid traversal and key collection constraints using a bitmask state. Showing a brute-force mindset first (treating each key combination as a state) demonstrates understanding, but implementing the optimized BFS with (row, col, mask) proves you can translate that idea into an efficient algorithm.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS with State Tracking (Bitmask) | O(m*n*2^k) | O(m*n*2^k) | General solution for grid shortest path with collectibles and locks |
| A* Search Algorithm | O(m*n*2^k) worst case | O(m*n*2^k) | Large grids where heuristic guidance can reduce exploration |
| Bidirectional BFS | O(m*n*2^k) | O(m*n*2^k) | When search depth is large and meeting in the middle reduces traversal |