This problem requires tracking key collection with bitmasks while exploring the grid via BFS. Each move must respect walls and locked doors, only allowing passage if the corresponding key is held. Using array positions combined with bit manipulation ensures efficient state tracking and guarantees the shortest path computation.
Problem Statement
You are given an m x n grid where '@' marks your starting position, '.' are empty spaces, lowercase letters are keys, and uppercase letters are locks. You can move in four directions and cannot pass through walls marked with '#'. Each move covers one cell.
Your goal is to collect all keys in the grid in the minimum number of steps. You can pick up a key by walking over it and can only pass through a lock if you have its matching key. Return the fewest steps required, or -1 if collecting all keys is impossible.
Examples
Example 1
Input: grid = ["@.a..","###.#","b.A.B"]
Output: 8
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 details omitted.
Example 3
Input: grid = ["@Aa"]
Output: -1
Example details omitted.
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.
Solution Approach
Use BFS with State Tracking
Perform a breadth-first search from the starting position, tracking not just coordinates but also the set of collected keys using a bitmask. Each BFS node represents a unique combination of position and keys.
Handle Locks with Bitmask Checks
Before moving into a cell with a lock, check if the corresponding bit in the key bitmask is set. This ensures only valid paths are explored, avoiding unnecessary BFS expansions that would fail due to missing keys.
Optimize State Memory
Maintain a visited set keyed by both position and current key bitmask to prevent revisiting states. This reduces redundant exploration and guarantees the algorithm runs within manageable space despite multiple key combinations.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(RC(2\mathcal{A} + 1) + \mathcal{E} \log \mathcal{N}) |
| Space | O(\mathcal{N}) |
Time complexity is O(RC(2^A + 1) + E log N) due to BFS across R*C positions with up to 2^A key combinations, where A is number of keys. Space complexity is O(N) for storing visited states for each position and key bitmask.
What Interviewers Usually Probe
- Expect questions on BFS combined with bitmasking for state representation.
- Watch for cases where multiple paths reach the same cell with different keys.
- Clarify handling of unreachable keys due to locked doors blocking all paths.
Common Pitfalls or Variants
Common pitfalls
- Forgetting to include the current key state in the visited set, causing cycles or incorrect answers.
- Trying to brute-force paths without pruning, leading to exponential time explosion.
- Incorrectly assuming keys can be collected in any order without considering locks.
Follow-up variants
- Grid sizes larger than 30x30 with more keys and locks to stress BFS efficiency.
- Grids where some keys are completely inaccessible unless others are collected first.
- Variants with multiple starting points requiring coordinated key collection.
How GhostInterview Helps
- GhostInterview generates the BFS and bitmask logic scaffolding for this exact pattern.
- It flags potential pitfalls like revisiting states without key tracking.
- The solver shows step counts and path reasoning for each key, speeding up interview explanation.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
How does bit manipulation help in Shortest Path to Get All Keys?
Each key is represented as a bit in an integer, allowing efficient checks and updates for collected keys, crucial for BFS state tracking.
What happens if a key is behind a lock?
You cannot pass through the lock until the corresponding key is collected, so BFS must explore alternative paths until the key is obtained.
Can we revisit a cell after picking up keys?
Yes, revisiting is allowed but must consider the current key bitmask to avoid redundant exploration of already visited states.
What is the maximum number of keys supported?
The problem restricts keys to a maximum of 6, which fits within a 6-bit integer for efficient bitmask representation.
Why BFS is preferred over DFS for this problem?
BFS ensures the minimum steps are found first, whereas DFS might explore longer paths and fail to guarantee the shortest path to collect all keys.
Need direct help with Shortest Path to Get All Keys instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Shortest Path to Get All Keys from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Compute the minimum flips to convert a binary matrix to zero by toggling cells and neighbors using array scanning plus hash lookup.
Open problem page#861 Score After Flipping MatrixMaximize the score of a binary matrix by flipping rows and columns using a greedy approach and validation of invariants.
Open problem page#832 Flipping an ImageFlip each row of a binary matrix horizontally and invert its values efficiently using a two-pointer scanning approach.
Open problem page