LeetCode #864 — HARD

Shortest Path to Get All Keys

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

The Problem

Problem Statement

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.

Step 01

Brute Force Baseline

Problem summary: 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Bit Manipulation

Example 1

["@.a..","###.#","b.A.B"]

Example 2

["@..aA","..B#.","....b"]

Example 3

["@Aa"]

Step 02

Core Insight

What unlocks the optimal approach

No official hints in dataset. Start from constraints and look for a monotonic or reusable state.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #864: Shortest Path to Get All Keys
class Solution {
    private int[] dirs = {-1, 0, 1, 0, -1};

    public int shortestPathAllKeys(String[] grid) {
        int m = grid.length, n = grid[0].length();
        int k = 0;
        int si = 0, sj = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                char c = grid[i].charAt(j);
                if (Character.isLowerCase(c)) {
                    // 累加钥匙数量
                    ++k;
                } else if (c == '@') {
                    // 起点
                    si = i;
                    sj = j;
                }
            }
        }
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {si, sj, 0});
        boolean[][][] vis = new boolean[m][n][1 << k];
        vis[si][sj][0] = true;
        int ans = 0;
        while (!q.isEmpty()) {
            for (int t = q.size(); t > 0; --t) {
                var p = q.poll();
                int i = p[0], j = p[1], state = p[2];
                // 找到所有钥匙，返回当前步数
                if (state == (1 << k) - 1) {
                    return ans;
                }
                // 往四个方向搜索
                for (int h = 0; h < 4; ++h) {
                    int x = i + dirs[h], y = j + dirs[h + 1];
                    // 在边界范围内
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        char c = grid[x].charAt(y);
                        // 是墙，或者是锁，但此时没有对应的钥匙，无法通过
                        if (c == '#'
                            || (Character.isUpperCase(c) && ((state >> (c - 'A')) & 1) == 0)) {
                            continue;
                        }
                        int nxt = state;
                        // 是钥匙
                        if (Character.isLowerCase(c)) {
                            // 更新状态
                            nxt |= 1 << (c - 'a');
                        }
                        // 此状态未访问过，入队
                        if (!vis[x][y][nxt]) {
                            vis[x][y][nxt] = true;
                            q.offer(new int[] {x, y, nxt});
                        }
                    }
                }
            }
            // 步数加一
            ++ans;
        }
        return -1;
    }
}

// Accepted solution for LeetCode #864: Shortest Path to Get All Keys
func shortestPathAllKeys(grid []string) int {
	m, n := len(grid), len(grid[0])
	var k, si, sj int
	for i, row := range grid {
		for j, c := range row {
			if c >= 'a' && c <= 'z' {
				// 累加钥匙数量
				k++
			} else if c == '@' {
				// 起点
				si, sj = i, j
			}
		}
	}
	type tuple struct{ i, j, state int }
	q := []tuple{tuple{si, sj, 0}}
	vis := map[tuple]bool{tuple{si, sj, 0}: true}
	dirs := []int{-1, 0, 1, 0, -1}
	ans := 0
	for len(q) > 0 {
		for t := len(q); t > 0; t-- {
			p := q[0]
			q = q[1:]
			i, j, state := p.i, p.j, p.state
			// 找到所有钥匙，返回当前步数
			if state == 1<<k-1 {
				return ans
			}
			// 往四个方向搜索
			for h := 0; h < 4; h++ {
				x, y := i+dirs[h], j+dirs[h+1]
				// 在边界范围内
				if x >= 0 && x < m && y >= 0 && y < n {
					c := grid[x][y]
					// 是墙，或者是锁，但此时没有对应的钥匙，无法通过
					if c == '#' || (c >= 'A' && c <= 'Z' && (state>>(c-'A')&1 == 0)) {
						continue
					}
					nxt := state
					// 是钥匙，更新状态
					if c >= 'a' && c <= 'z' {
						nxt |= 1 << (c - 'a')
					}
					// 此状态未访问过，入队
					if !vis[tuple{x, y, nxt}] {
						vis[tuple{x, y, nxt}] = true
						q = append(q, tuple{x, y, nxt})
					}
				}
			}
		}
		// 步数加一
		ans++
	}
	return -1
}

# Accepted solution for LeetCode #864: Shortest Path to Get All Keys
class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m, n = len(grid), len(grid[0])
        # 找起点 (si, sj)
        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

// Accepted solution for LeetCode #864: Shortest Path to Get All Keys
/**
 * [0864] Shortest Path to Get All Keys
 *
 * 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 <font face="monospace">1 <= k <= 6</font>, 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.
 *  
 * <strong class="example">Example 1:
 * <img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-keys2.jpg" style="width: 404px; height: 245px;" />
 * 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.
 *
 * <strong class="example">Example 2:
 * <img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-key2.jpg" style="width: 404px; height: 245px;" />
 * Input: grid = ["@..aA","..B#.","....b"]
 * Output: 6
 *
 * <strong class="example">Example 3:
 * <img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-keys3.jpg" style="width: 244px; height: 85px;" />
 * 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 '@'.
 * 	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.
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/shortest-path-to-get-all-keys/
// discuss: https://leetcode.com/problems/shortest-path-to-get-all-keys/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

// Credit: https://leetcode.com/problems/shortest-path-to-get-all-keys/solutions/839020/rust-translated-24ms-100/

#[derive(Debug, Eq, PartialEq, Hash, Clone)]
struct State {
    i: i32,
    j: i32,
    keys: i32,
}

impl Solution {
    pub fn shortest_path_all_keys(grid: Vec<String>) -> i32 {
        const DIRS: [i32; 5] = [0, -1, 0, 1, 0];

        let m = grid.len();
        let n = grid[0].len();
        let mut i = -1i32;
        let mut j = -1i32;
        let mut max = 0;
        for x in 0..m {
            for y in 0..n {
                let c = grid[x].as_bytes()[y];
                if c == b'@' {
                    i = x as i32;
                    j = y as i32;
                } else if c >= b'a' && c <= b'f' {
                    max = std::cmp::max(max, c - b'a' + 1);
                }
            }
        }

        let mut all_keys = (1 << max) - 1;

        let mut visited = std::collections::HashSet::<State>::new();
        let mut queue = std::collections::VecDeque::<State>::new();
        let start = State { i, j, keys: 0 };
        visited.insert(start.clone());
        queue.push_back(start);
        let mut step = 0;
        while !queue.is_empty() {
            let mut size = queue.len();
            while size > 0 {
                size -= 1;
                let curr = queue.pop_front().unwrap();
                if curr.keys == all_keys {
                    return step;
                }
                for k in 0..4 {
                    let x = curr.i + DIRS[k];
                    let y = curr.j + DIRS[k + 1];
                    if x < 0 || x >= m as i32 || y < 0 || y >= n as i32 {
                        continue;
                    }
                    let c = grid[x as usize].as_bytes()[y as usize];
                    if c == b'#' {
                        continue;
                    }
                    if c >= b'A' && c <= b'F' && (curr.keys & (1 << (c - b'A'))) == 0 {
                        continue;
                    }
                    let mut keys = curr.keys;
                    if c >= b'a' && c <= b'f' {
                        keys |= (1 << (c - b'a'));
                    }
                    let next = State { i: x, j: y, keys };
                    if visited.contains(&next) {
                        continue;
                    }
                    visited.insert(next.clone());
                    queue.push_back(next);
                }
            }
            step += 1;
        }
        -1
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_0864_example_1() {
        let grid = vec_string!["@.a..", "###.#", "b.A.B"];
        let result = 8;

        assert_eq!(Solution::shortest_path_all_keys(grid), result);
    }

    #[test]
    fn test_0864_example_2() {
        let grid = vec_string!["@..aA", "..B#.", "....b"];
        let result = 6;

        assert_eq!(Solution::shortest_path_all_keys(grid), result);
    }

    #[test]
    fn test_0864_example_3() {
        let grid = vec_string!["@Aa"];
        let result = -1;

        assert_eq!(Solution::shortest_path_all_keys(grid), result);
    }
}

// Accepted solution for LeetCode #864: Shortest Path to Get All Keys
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #864: Shortest Path to Get All Keys
// class Solution {
//     private int[] dirs = {-1, 0, 1, 0, -1};
// 
//     public int shortestPathAllKeys(String[] grid) {
//         int m = grid.length, n = grid[0].length();
//         int k = 0;
//         int si = 0, sj = 0;
//         for (int i = 0; i < m; ++i) {
//             for (int j = 0; j < n; ++j) {
//                 char c = grid[i].charAt(j);
//                 if (Character.isLowerCase(c)) {
//                     // 累加钥匙数量
//                     ++k;
//                 } else if (c == '@') {
//                     // 起点
//                     si = i;
//                     sj = j;
//                 }
//             }
//         }
//         Deque<int[]> q = new ArrayDeque<>();
//         q.offer(new int[] {si, sj, 0});
//         boolean[][][] vis = new boolean[m][n][1 << k];
//         vis[si][sj][0] = true;
//         int ans = 0;
//         while (!q.isEmpty()) {
//             for (int t = q.size(); t > 0; --t) {
//                 var p = q.poll();
//                 int i = p[0], j = p[1], state = p[2];
//                 // 找到所有钥匙，返回当前步数
//                 if (state == (1 << k) - 1) {
//                     return ans;
//                 }
//                 // 往四个方向搜索
//                 for (int h = 0; h < 4; ++h) {
//                     int x = i + dirs[h], y = j + dirs[h + 1];
//                     // 在边界范围内
//                     if (x >= 0 && x < m && y >= 0 && y < n) {
//                         char c = grid[x].charAt(y);
//                         // 是墙，或者是锁，但此时没有对应的钥匙，无法通过
//                         if (c == '#'
//                             || (Character.isUpperCase(c) && ((state >> (c - 'A')) & 1) == 0)) {
//                             continue;
//                         }
//                         int nxt = state;
//                         // 是钥匙
//                         if (Character.isLowerCase(c)) {
//                             // 更新状态
//                             nxt |= 1 << (c - 'a');
//                         }
//                         // 此状态未访问过，入队
//                         if (!vis[x][y][nxt]) {
//                             vis[x][y][nxt] = true;
//                             q.offer(new int[] {x, y, nxt});
//                         }
//                     }
//                 }
//             }
//             // 步数加一
//             ++ans;
//         }
//         return -1;
//     }
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(m × n × 2^k)

Space

O(m × n × 2^k)

Approach Breakdown

SORT + SCAN

O(n log n) time

O(n) space

Sort the array in O(n log n), then scan for the missing or unique element by comparing adjacent pairs. Sorting requires O(n) auxiliary space (or O(1) with in-place sort but O(n log n) time remains). The sort step dominates.

BIT MANIPULATION

O(n) time

O(1) space

Bitwise operations (AND, OR, XOR, shifts) are O(1) per operation on fixed-width integers. A single pass through the input with bit operations gives O(n) time. The key insight: XOR of a number with itself is 0, which eliminates duplicates without extra space.

Shortcut: Bit operations are O(1). XOR cancels duplicates. Single pass → O(n) time, O(1) space.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.