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].The problem is a grid-based search where a player must collect all keys while navigating walls, locks, and open cells. The most effective strategy is to use Breadth-First Search (BFS) because we need the shortest number of steps. However, the challenge is that the state depends not only on the position in the grid but also on the set of keys collected.
To handle this, represent the collected keys using a bitmask. Each BFS state can be modeled as (row, col, keyMask), where keyMask tracks which keys have been collected so far. When encountering a key, update the mask using bit manipulation. When encountering a lock, you can only pass if the corresponding bit is already set.
To avoid revisiting redundant states, maintain a visited structure that includes both position and key state. BFS continues until the bitmask indicates that all keys are collected. The overall complexity depends on the grid size and the number of possible key states, leading to approximately O(m * n * 2^k) states where k is the number of keys.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| BFS with Bitmask State Tracking | O(m * n * 2^k) | O(m * n * 2^k) |
Aryan Mittal
This approach uses a Breadth-First Search (BFS) to explore the grid. The idea is to treat the grid like a graph, where each cell is a node, and transitions between them are edges. Since we can pick up keys and unlock doors, each state is defined by the current position in the grid and the set of keys we have collected so far. The BFS will explore all possible moves, and we store the visited states to prevent redundant processing. The search continues until all keys are collected or all possible states are exhausted.
Time Complexity: O(m * n * 2^k), where m and n are the dimensions of the grid and k is the number of keys.
Space Complexity: O(m * n * 2^k), due to the visited states tracking.
1from collections import deque
2
3def shortest_path_to_get_all_keys(grid):
4 m, n = len(grid), len(grid[0])
5 dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
6 all_keys = 0
7 start = None
8
9 for i in range(m):
10 for j in range(n):
11 if grid[i][j] == '@':
12 start = (i, j)
13 elif 'a' <= grid[i][j] <= 'f':
14 all_keys |= (1 << (ord(grid[i][j]) - ord('a')))
15
16 queue = deque([(start[0], start[1], 0)])
17 visited = set([(start[0], start[1], 0)])
18 steps = 0
19
20 while queue:
21 for _ in range(len(queue)):
22 x, y, keys = queue.popleft()
23
24 if keys == all_keys:
25 return steps
26
27 for dx, dy in dirs:
28 nx, ny = x + dx, y + dy
29
30 if 0 <= nx < m and 0 <= ny < n:
31 cell = grid[nx][ny]
32
33 if cell == '#':
34 continue
35
36 if 'A' <= cell <= 'F' and not (keys & (1 << (ord(cell) - ord('A')))):
37 continue
38
39 new_keys = keys
40 if 'a' <= cell <= 'f':
41 new_keys |= (1 << (ord(cell) - ord('a')))
42
43 if (nx, ny, new_keys) not in visited:
44 visited.add((nx, ny, new_keys))
45 queue.append((nx, ny, new_keys))
46
47 steps += 1
48
49 return -1
50The Python solution implements a BFS to explore the grid. It uses a queue to store current states, defined by position and keys collected. The solution initializes by finding the starting position and counting all keys needed. The BFS loop processes each state, trying all possible moves, and keeps track of visited states to prevent cycles. When all keys are collected, the function returns the steps taken; if exploration is exhausted and not all keys are collected, it returns -1.
This approach uses the A* search algorithm, which is similar to BFS but uses a heuristic to prioritize nodes that appear most promising. The heuristic can be the number of keys left to collect or the Manhattan distance to nearest unexplored keys. Like BFS, we define states by position and keys collected, and employ a priority queue to explore states in an order influenced by the heuristic. This modification aims to reduce the time spent searching unproductive paths.
Time Complexity: O(m * n * 2^k), where m and n are the grid dimensions and k is the number of keys. The heuristic aids in reducing the actual search space.
Space Complexity: O(m * n * 2^k), since states are tracked in the priority queue.
1import heapq
2
3def heuristic(keys, all_keys)
This approach attempts to optimize the BFS by implementing a bidirectional search. Starting a BFS from both the starting point and from the theoretical point where all keys are collected, the search works concurrently from both ends hoping to meet sooner, theoretically reducing the effective search space.
Time Complexity: The expected complexity can still be O(m * n * 2^k) but theoretically with bidirectional capabilities lowering the average active search space time.
Space Complexity: Also O(m * n * 2^k) due to potential full state coverage retaining visited states for bidirectional expansion points.
1#include <vector>
2#include <queue>
3#include <unordered_map>
4#include <unordered_set>
5#include <string>
6using namespace std;
7
struct State {
int x, y, keys;
State(int x, int y, int keys) : x(x), y(y), keys(keys) {}
};
int shortestPathAllKeys(vector<string>& grid) {
int m = grid.size(), n = grid[0].size(), allKeys = 0;
queue<pair<State, int>> q;
unordered_set<string> visited;
int start_x, start_y;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
char c = grid[i][j];
if (c == '@') {
start_x = i; start_y = j;
}
else if (islower(c)) {
allKeys |= (1 << (c - 'a'));
}
}
}
q.push({ State(start_x, start_y, 0), 0 });
visited.insert(to_string(start_x) + "," + to_string(start_y) + ",0");
vector<pair<int, int>> directions = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
while (!q.empty()) {
auto [state, steps] = q.front(); q.pop();
if (state.keys == allKeys) return steps;
for (auto [dx, dy] : directions) {
int nx = state.x + dx, ny = state.y + dy;
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
char cell = grid[nx][ny];
if (cell == '#') continue;
int new_keys = state.keys;
if (islower(cell)) new_keys |= (1 << (cell - 'a'));
if (isupper(cell) && !(new_keys & (1 << (cell - 'A')))) continue;
string new_state = to_string(nx) + "," + to_string(ny) + "," + to_string(new_keys);
if (visited.find(new_state) == visited.end()) {
visited.insert(new_state);
q.push({State(nx, ny, new_keys), steps + 1});
}
}
}
return -1;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem reflects common interview themes like grid traversal, BFS, and state compression using bitmasks. Variations of this problem frequently appear in FAANG-style interviews to test algorithmic thinking and state management.
Bit manipulation efficiently represents the set of collected keys. Instead of storing sets or arrays, a bitmask allows constant-time checks and updates when picking up keys or unlocking doors.
The optimal approach uses Breadth-First Search (BFS) combined with bitmasking to track collected keys. Each BFS state includes the grid position and the current key set, ensuring the algorithm finds the minimum number of steps to gather all keys.
A queue is used for BFS traversal to guarantee the shortest path. Additionally, a visited structure such as a 3D boolean array or hash set is used to track visited states defined by position and key mask.
The Python solution applies the A* search technique. We use a priority queue to handle states, including heuristic-driven priority. States are evaluated based on current path cost and estimated remaining cost, guided by the heuristic that counts keys not collected yet. The solution efficiently navigates the grid, updating keys collected and prioritizing paths that bring us closer to the final state. If paths are exhausted without collecting all keys, the solution returns -1.
This C++ solution follows a similar path to the BFS approach but refines it with bidirectional BFS. Starting the BFS from the initial grid position and theoretically completing goal states, it uses a queue to manage and traverse levels. Each possible path through grid updating states based on reachable keys. Like the unidirectional BFS but optimized from exploring both ends.