Compute shortest path to collect all keys
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an m×n grid containing walls (#), open cells (.), a single start cell (@), up to six keys labeled 'a'–'f', and matching doors 'A'–'F' that can be passed only after obtaining their corresponding key. From any cell, you may move one step up, down, left, or right to an in-bounds non-wall cell. Return the minimum number of steps required to collect all keys, or -1 if it is impossible. Handle m, n up to 30. Describe your state representation, search strategy, pruning, and how you detect revisits efficiently. Provide time and space complexity and key test cases.
Quick Answer: This question evaluates proficiency in state-space representation, graph search and shortest-path techniques, compact state encoding (such as bitmasking), and algorithmic time/space complexity analysis within the Coding & Algorithms domain.
You are given a rectangular grid represented as a list of strings. Each cell contains one of the following characters: '#' for a wall, '.' for an open cell, '@' for the single starting cell, lowercase letters 'a' to 'f' for keys, and uppercase letters 'A' to 'F' for doors. You may move one step up, down, left, or right onto any in-bounds cell that is not a wall. A door can be entered only if you have already collected its corresponding lowercase key. Return the minimum number of steps required to collect all keys, or -1 if it is impossible. Because the set of collected keys changes what doors you can pass, reaching the same grid cell with different key sets must be treated as different search states. Your solution should be efficient for grids up to 30 x 30.
Constraints
- 1 <= m, n <= 30
- grid[i][j] is one of '#', '.', '@', 'a' - 'f', or 'A' - 'F'
- There is exactly one starting cell '@'
- There are at most 6 keys, and each door matches a key with the same letter ignoring case
Examples
Input: (["@.a..","###.#","b.A.B"],)
Expected Output: 8
Explanation: You must collect 'a' first, then pass through door 'A' to eventually reach 'b'. The shortest valid route takes 8 steps.
Input: (["@..aA","..B#.","....b"],)
Expected Output: 6
Explanation: Collect 'a' in 3 steps, then move through door 'A' and continue to 'b'. The minimum is 6.
Hints
- A normal BFS over just (row, col) is not enough, because arriving at the same cell with different keys collected can lead to different future moves.
- Since there are at most 6 keys, encode the collected keys as a bitmask and use (row, col, key_mask) as your BFS state and visited marker.