Open the Lock

Medium · Graphs · Explanation and code example

Bidirectional Breadth First Search

How it works

Standard BFS explores outward from the start, which can lead to exploring many states before reaching a distant target. Bidirectional BFS improves this by searching from both ends simultaneously: one frontier starts at "0000" and another at the target. When they meet, we've found the shortest path.

The key optimization is to always expand the smaller frontier. This balances the search and reduces the total number of states explored, especially when the search space branches heavily in one direction.

Steps

  1. Handle edge cases for target "0000" and "0000" being a deadend.
  2. Create two sets: begin starting from "0000" and end starting from target.
  3. While both sets are non-empty:
    • If begin is larger than end, swap them to always expand the smaller one.
    • Increment steps and create a temporary set for the next level.
    • For each state in begin, generate all 8 neighbors.
    • If a neighbor is in end, the frontiers meet, so return steps.
    • Otherwise, if unvisited, add to the temp set and mark visited.
    • Replace begin with the temp set.
  4. Return -1 if the sets never meet.

Complexity

  • Time complexity: O(d ^ n + m)
  • Space complexity: O(d ^ n)

Where d is the number of digits (0 - 9), n is the number of wheels (4), and m is the number of deadends.

Things to watch for

Not Checking if Starting Position is a Deadend

The initial state "0000" might itself be a deadend. Failing to check this before starting BFS leads to incorrect exploration from an invalid starting point. Always verify "0000" is not in the deadends set before beginning the search.

Incorrect Wheel Wraparound Logic

Turning a wheel from 9 up should go to 0, and turning from 0 down should go to 9. Using simple addition/subtraction without modular arithmetic causes invalid states like -1 or 10. Apply (digit + move + 10) % 10 to handle wraparound correctly.

Adding to Visited Set After Dequeuing Instead of Before Enqueuing

Marking nodes as visited when dequeuing rather than when enqueuing leads to the same state being added to the queue multiple times. This causes redundant processing and can significantly slow down the solution. Always mark a state as visited immediately when adding it to the queue.

Python code example

from typing import List

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        if target == "0000":
            return 0

        visit = set(deadends)
        if "0000" in visit:
            return -1

        begin = {"0000"}
        end = {target}
        steps = 0

        while begin and end:
            if len(begin) > len(end):
                begin, end = end, begin

            steps += 1
            temp = set()
            for lock in begin:
                for i in range(4):
                    for j in [-1, 1]:
                        digit = str((int(lock[i]) + j + 10) % 10)
                        nextLock = lock[:i] + digit + lock[i+1:]

                        if nextLock in end:
                            return steps
                        if nextLock in visit:
                            continue
                        visit.add(nextLock)
                        temp.add(nextLock)
            begin = temp
        return -1

C++ code example

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        if (target == "0000") return 0;

        unordered_set<string> visit(deadends.begin(), deadends.end());
        if (visit.count("0000")) return -1;

        unordered_set<string> begin = {"0000"}, end = {target};
        int steps = 0;

        while (!begin.empty() && !end.empty()) {
            if (begin.size() > end.size()) swap(begin, end);
            steps++;
            unordered_set<string> temp;

            for (const string& lock : begin) {
                for (int i = 0; i < 4; ++i) {
                    for (int j : {-1, 1}) {
                        string nextLock = lock;
                        nextLock[i] = (nextLock[i] - '0' + j + 10) % 10 + '0';

                        if (end.count(nextLock)) return steps;
                        if (visit.count(nextLock)) continue;

                        visit.insert(nextLock);
                        temp.insert(nextLock);
                    }
                }
            }
            begin = temp;
        }
        return -1;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations