Shortest Path to Get All Keys

Hard Graphs BFS for shortest path Original on LeetCode

Reported atPhonePe

Shortest Path to Get All Keys is a hard graphs problem solved with the bfs for shortest path pattern. The best approach, optimal (bfs over cell + key mask), runs in O(m · n · 2^k) time and O(m · n · 2^k) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every key order) up.

Problem

You are given a grid as an array of equal-length strings. Each cell is one of:

  • '.' an empty cell, '#' a wall, '@' your starting cell;
  • a lowercase letter: a key; an uppercase letter: a lock, which can only be entered once you hold the key with the same letter.

In one move you step to a neighbouring cell up, down, left or right. You cannot leave the grid or enter a wall. Stepping on a key picks it up.

Return the fewest moves needed to collect all keys in the grid, or -1 if that is impossible.

Examples

Example 1

Input
grid = ["@.a.#", "###.#", "b.A.B"]
Output
8
Why
Walk right to a (2 moves), go around through (0,3), (1,3), (2,3) (3 moves), then pass the lock A with key a and reach b (3 moves).

Example 2

Input
grid = ["a.@.b"]
Output
6
Why
Two steps left to a, then four steps right to b.

Example 3

Input
grid = ["@Aa"]
Output
-1
Why
The only way to key a goes through lock A, which needs key a.

Constraints

  • 1 <= m, n <= 30 where m = grid.length and n = grid[i].length
  • grid[i][j] is one of '.', '#', '@', a lowercase letter or an uppercase letter.
  • Exactly one '@'.
  • There are k keys with 1 <= k <= 6; they are the first k lowercase letters, each appearing once.
  • Every lock is the uppercase form of one of those keys.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 16 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every key order)O(k! · k · m · n)O(m · n)
Optimal (BFS over cell + key mask)O(m · n · 2^k)O(m · n · 2^k)

1Brute force (try every key order)

TimeO(k! · k · m · n)Up to 720 orders, each with k BFS runs over the grid.
SpaceO(m · n)The BFS distance table and queue.

Any route collects the keys in some order. For each of the k! orders, walk from the start to the first key, then to the next, and so on, each leg being a plain grid BFS that may only pass locks whose keys were collected on earlier legs. The cheapest total over all orders is the answer.

  1. Find the start cell and the position of each key; let k be the number of keys.
  2. Generate every permutation of the k keys.
  3. For one permutation: from the current cell, BFS to the next key with the keys held so far; if unreachable, the order fails; otherwise add the distance and add that key.
  4. Return the minimum total over all orders, or -1 if every order fails.
class Solution {
    private String[] grid;
    private int m, n;
    private int[] keyR = new int[6], keyC = new int[6];
    private int best = Integer.MAX_VALUE;

    public int shortestPathAllKeys(String[] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length();
        int sr = 0, sc = 0, k = 0;
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++) {
                char ch = grid[r].charAt(c);
                if (ch == '@') { sr = r; sc = c; }
                else if (ch >= 'a' && ch <= 'f') {
                    keyR[ch - 'a'] = r;
                    keyC[ch - 'a'] = c;
                    k++;
                }
            }
        permute(new int[k], new boolean[k], 0, sr, sc);
        return best == Integer.MAX_VALUE ? -1 : best;
    }

    private void permute(int[] order, boolean[] used, int pos, int sr, int sc) {
        if (pos == order.length) {
            int total = 0, mask = 0, r = sr, c = sc;
            for (int key : order) {
                int d = bfs(r, c, keyR[key], keyC[key], mask);
                if (d < 0) return;
                total += d;
                mask |= 1 << key;
                r = keyR[key];
                c = keyC[key];
            }
            best = Math.min(best, total);
            return;
        }
        for (int i = 0; i < order.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            order[pos] = i;
            permute(order, used, pos + 1, sr, sc);
            used[i] = false;
        }
    }

    private int bfs(int sr, int sc, int tr, int tc, int mask) {
        int[][] dist = new int[m][n];
        for (int[] row : dist) Arrays.fill(row, -1);
        ArrayDeque<int[]> q = new ArrayDeque<>();
        dist[sr][sc] = 0;
        q.add(new int[] { sr, sc });
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            if (cur[0] == tr && cur[1] == tc) return dist[tr][tc];
            for (int[] d : dirs) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr < 0 || nc < 0 || nr >= m || nc >= n || dist[nr][nc] >= 0) continue;
                char ch = grid[nr].charAt(nc);
                if (ch == '#') continue;
                if (ch >= 'A' && ch <= 'F' && ((mask >> (ch - 'A')) & 1) == 0) continue;
                dist[nr][nc] = dist[cur[0]][cur[1]] + 1;
                q.add(new int[] { nr, nc });
            }
        }
        return -1;
    }
}

2Optimal (BFS over cell + key mask)

TimeO(m · n · 2^k)Each of the m · n · 2^k states is visited once with 4 moves; at most 900 · 64 states.
SpaceO(m · n · 2^k)The seen table and the queue over all states.

Run one BFS whose states are (row, col, mask), where mask records the keys collected. Stepping onto a key sets its bit; a lock can be entered only if its bit is set; walls are never entered. Because every move costs 1, the first time BFS pops a state whose mask has all keys, its distance is the shortest route.

  1. Scan the grid for the start and build full = (1 << k) - 1.
  2. seen[r][c][mask] marks visited states; push (start, mask 0) with distance 0.
  3. Process the queue level by level; if mask == full return the current distance.
  4. For each of 4 neighbours: skip walls, out-of-range cells and locks without their key; add a key bit if the cell holds a key; push unseen states.
  5. If the queue empties, return -1.
class Solution {
    public int shortestPathAllKeys(String[] grid) {
        int m = grid.length, n = grid[0].length();
        int sr = 0, sc = 0, k = 0;
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++) {
                char ch = grid[r].charAt(c);
                if (ch == '@') { sr = r; sc = c; }
                else if (ch >= 'a' && ch <= 'f') k++;
            }
        int full = (1 << k) - 1;
        boolean[][][] seen = new boolean[m][n][1 << k];
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.add(new int[] { sr, sc, 0 });
        seen[sr][sc][0] = true;
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        int steps = 0;
        while (!q.isEmpty()) {
            for (int size = q.size(); size > 0; size--) {
                int[] cur = q.poll();
                if (cur[2] == full) return steps;
                for (int[] d : dirs) {
                    int nr = cur[0] + d[0], nc = cur[1] + d[1];
                    if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
                    char ch = grid[nr].charAt(nc);
                    if (ch == '#') continue;
                    if (ch >= 'A' && ch <= 'F' && ((cur[2] >> (ch - 'A')) & 1) == 0) continue;
                    int mask = cur[2];
                    if (ch >= 'a' && ch <= 'f') mask |= 1 << (ch - 'a');
                    if (!seen[nr][nc][mask]) {
                        seen[nr][nc][mask] = true;
                        q.add(new int[] { nr, nc, mask });
                    }
                }
            }
            steps++;
        }
        return -1;
    }
}

Edge cases to test

  • A key is unreachable, or locked behind its own lock: return -1
  • The best route visits keys in an order that is not the nearest-first order
  • Walking back over cells already visited, after picking up a key
  • A 1-row grid

Hints

Hint 1

Plain BFS on cells is not enough: the same cell may need to be visited again after you pick up a new key.

Hint 2

Make the state (row, column, set of keys held). Store the key set as a bitmask of at most 6 bits.

Hint 3

BFS over these states; the first state holding all keys gives the answer.

FAQ

What is the best time complexity for Shortest Path to Get All Keys?

Optimal (BFS over cell + key mask) runs in O(m · n · 2^k) time and O(m · n · 2^k) extra space. Each of the m · n · 2^k states is visited once with 4 moves; at most 900 · 64 states.

Which pattern does Shortest Path to Get All Keys use?

It is a graphs problem that uses the bfs for shortest path pattern. Other problems with the same pattern: Shortest Path in Binary Matrix, Word Ladder, Bus Routes.

Is there a brute force solution for Shortest Path to Get All Keys?

Yes. Brute force (try every key order) takes O(k! · k · m · n) time and O(m · n) space. Any route collects the keys in some order.

Which edge cases should I test for Shortest Path to Get All Keys?

A key is unreachable, or locked behind its own lock: return -1; The best route visits keys in an order that is not the nearest-first order; Walking back over cells already visited, after picking up a key; A 1-row grid.