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

The optimal solution has a time complexity of O(m*n*2^k).

What is the space complexity of Shortest Path to Get All Keys?

The space complexity is O(m*n*2^k).

What data structures are used to solve Shortest Path to Get All Keys?

This problem uses Array, Bit Manipulation, Breadth-First Search, Matrix. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Shortest Path to Get All Keys?

Insight 1: The state of the search needs to include the current position (row, col) and the set of keys collected so far, represented as a bitmask. Insight 2: Breadth-First Search (BFS) is suitable for finding the shortest path in an unweighted graph (where each move has a cost of 1).

Which companies ask LeetCode 864. Shortest Path to Get All Keys in interviews?

This problem is frequently asked at Airbnb, Pinterest, Roku.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Shortest Path to Get All Keys - LeetCode 864 Solution

Q: How to solve Shortest Path to Get All Keys?

The provided solutions use Breadth-First Search (BFS) to explore the grid. Each state in the BFS queue is represented by the current row, column, and a bitmask indicating which keys have been collected. The algorithm explores possible moves from each state, updating the keymask when a new key is found. It checks if a move is valid (not a wall, not outside the grid, and has the required key for a lock). A set `visited` is used to avoid revisiting states, where a state is defined by row, col and the key bitmask. The algorithm continues until all keys are collected or the queue is empty (indicating no path exists).

Shortest Path to Get All Keys - Complete Solution Guide

Shortest Path to Get All Keys is LeetCode problem 864, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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

Detailed Explanation

The problem requires finding the shortest path to collect all keys in a grid. The grid contains empty cells ('.'), walls ('#'), a starting point ('@'), keys (lowercase letters), and locks (uppercase letters). You can move in four cardinal directions, pick up keys upon encountering them, and open locks only if you possess the corresponding key. The goal is to determine the minimum number of moves needed to acquire all keys. If acquiring all keys is impossible, return -1.

Solution Approach

The provided solutions use Breadth-First Search (BFS) to explore the grid. Each state in the BFS queue is represented by the current row, column, and a bitmask indicating which keys have been collected. The algorithm explores possible moves from each state, updating the keymask when a new key is found. It checks if a move is valid (not a wall, not outside the grid, and has the required key for a lock). A set `visited` is used to avoid revisiting states, where a state is defined by row, col and the key bitmask. The algorithm continues until all keys are collected or the queue is empty (indicating no path exists).

Step-by-Step Algorithm

Step 1: Initialize variables: grid dimensions, starting position, total number of keys, and the target keymask (all keys collected).
Step 2: Create a queue for BFS, initialize the starting state (starting row, starting column, empty keymask), and a set to track visited states.
Step 3: Perform BFS: While the queue is not empty, process nodes level by level (to guarantee shortest path).
Step 4: For each node in the current level, check if the current keymask equals the target keymask. If so, return the current step count.
Step 5: Explore possible moves (up, down, left, right).
Step 6: For each move, check if it is valid (within grid bounds and not a wall). Also check if we have the necessary key to open a lock if we encounter one. If a lock exists but the corresponding key isn't in the current mask, the move is invalid.
Step 7: If the move is valid, update the keymask if a key is encountered. Then, add the new state to the queue and the visited set, only if the new state was never previously visited.
Step 8: Increment the step count after processing each level of the queue.
Step 9: If the queue becomes empty before finding all keys, return -1 (no path exists).

Key Insights

Insight 1: The state of the search needs to include the current position (row, col) and the set of keys collected so far, represented as a bitmask.
Insight 2: Breadth-First Search (BFS) is suitable for finding the shortest path in an unweighted graph (where each move has a cost of 1).
Insight 3: The maximum number of keys is limited to 6, making it feasible to represent the key set as a bitmask (2^6 = 64 possible key combinations).

Complexity Analysis

Time Complexity: O(m*n*2^k)

Space Complexity: O(m*n*2^k)

Topics

This problem involves: Array, Bit Manipulation, Breadth-First Search, Matrix.

Companies

Asked at: Airbnb, Pinterest, Roku.

Shortest Path to Get All Keys | LeetCode 864

Hard

Array Bit Manipulation Breadth-First Search Matrix

Time: O(m*n*2^k)Space: O(m*n*2^k)

Solution Code

Available in:

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;

class Solution {
    public int shortestPathAllKeys(String[] grid) {
        int m = grid.length;
        int n = grid[0].length();

        int startRow = -1, startCol = -1;
        int totalKeys = 0;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r].charAt(c) == '@') {
                    startRow = r;
                    startCol = c;
                } else if (grid[r].charAt(c) >= 'a' && grid[r].charAt(c) <= 'f') {
                    totalKeys++;
                }
            }
        }

        int targetMask = (1 << totalKeys) - 1;

        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{startRow, startCol, 0});
        Set<String> visited = new HashSet<>();
        visited.add(startRow + "," + startCol + "," + 0);
        int steps = 0;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                int[] curr = queue.poll();
                int r = curr[0];
                int c = curr[1];
                int mask = curr[2];

                if (mask == targetMask) {
                    return steps;
                }

                int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
                for (int[] dir : directions) {
                    int nr = r + dir[0];
                    int nc = c + dir[1];

                    if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                        char cell = grid[nr].charAt(nc);

                        if (cell == '#') {
                            continue;
                        }

                        if (cell >= 'A' && cell <= 'F' && (mask & (1 << (cell - 'A'))) == 0) {
                            continue;
                        }

                        int newMask = mask;
                        if (cell >= 'a' && cell <= 'f') {
                            newMask |= (1 << (cell - 'a'));
                        }

                        String newState = nr + "," + nc + "," + newMask;
                        if (!visited.contains(newState)) {
                            visited.add(newState);
                            queue.offer(new int[]{nr, nc, newMask});
                        }
                    }
                }
            }
            steps++;
        }

        return -1;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 864: Shortest Path to Get All Keys - Detailed explanation and solution approaches.

Topics

Array Bit Manipulation Breadth-First Search Matrix

Companies

AirbnbPinterestRoku

Stats

Difficulty:Hard

Languages:4

Companies:3

Problem #:864

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: Initialize variables: grid dimensions, starting position, total number of keys, and the target keymask (all keys collected).
2
Step 2: Create a queue for BFS, initialize the starting state (starting row, starting column, empty keymask), and a set to track visited states.
3
Step 3: Perform BFS: While the queue is not empty, process nodes level by level (to guarantee shortest path).
4
Step 4: For each node in the current level, check if the current keymask equals the target keymask. If so, return the current step count.
5
Step 5: Explore possible moves (up, down, left, right).
6
Step 6: For each move, check if it is valid (within grid bounds and not a wall). Also check if we have the necessary key to open a lock if we encounter one. If a lock exists but the corresponding key isn't in the current mask, the move is invalid.
7
Step 7: If the move is valid, update the keymask if a key is encountered. Then, add the new state to the queue and the visited set, only if the new state was never previously visited.
8
Step 8: Increment the step count after processing each level of the queue.
9
Step 9: If the queue becomes empty before finding all keys, return -1 (no path exists).

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(m*n*2^k)

💾

Space Complexity

O(m*n*2^k)

📝

Why?

The time and space complexity are determined by the number of states the BFS algorithm might explore. Each state is defined by a cell in the grid (m*n possibilities) and the combination of keys collected (2^k possibilities). The BFS algorithm visits each state at most once due to the 'visited' set.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

A*

A* search could be used as an alternative. A heuristic function could be designed to estimate the number of steps to obtain the remaining keys. For example, the Manhattan distance to the closest uncollected key.

Time: In the worst case, similar to BFS: O(m*n*2^k), but can be faster in practice if the heuristic is well-chosen.Space: O(m*n*2^k) in the worst case.

Trade-offs: A* may perform better than BFS in certain scenarios due to the heuristic guiding the search, but it requires a good heuristic function. If the heuristic is poorly designed, the performance could degrade to be worse than BFS. For A* to be admissible, the heuristic must never overestimate the remaining cost to reach the target.

✨

Key Insights

1Insight 1: The state of the search needs to include the current position (row, col) and the set of keys collected so far, represented as a bitmask.
2Insight 2: Breadth-First Search (BFS) is suitable for finding the shortest path in an unweighted graph (where each move has a cost of 1).
3Insight 3: The maximum number of keys is limited to 6, making it feasible to represent the key set as a bitmask (2^6 = 64 possible key combinations).

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Edge Cases

Edge case 1: Grid with no keys. The algorithm should correctly identify the starting point and, since the target mask is 0, immediately return 0.
Edge case 2: Impossible scenario where a key is unreachable due to walls or locks. The algorithm correctly returns -1 after exploring all reachable states without collecting all keys.
Edge case 3: Grid with a single key and its corresponding lock placed in a way that the agent must collect the key before unlocking the lock. The program returns the shortest path length.
Edge case 4: The start point and target are the same. The number of moves should be 0.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not considering the key requirements for opening locks. This can lead to incorrect paths being explored and incorrect results.

✗Common mistake 2: Forgetting to use a 'visited' set or not properly defining the state (row, col, keymask), causing infinite loops and incorrect results. Defining the visited state correctly is crucial.

✗Common mistake 3: Incorrectly calculating the target keymask or misinterpreting the bitwise operations for managing the key set.

✗Common mistake 4: Using Depth-First Search (DFS) instead of BFS. DFS will not guarantee the shortest path.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Pathfinding in a game where the player needs to collect items (keys) to unlock areas (doors).

🏦Real-world scenario 2: Robot navigation in a warehouse or manufacturing environment where certain areas require specific authorizations (keys) to access.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Hard problems often combine multiple techniques. Break the problem into sub-problems.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 23, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Shortest Path to Get All Keys"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether bit manipulation techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?