Open the Lock

The Open the Lock problem is a classic graph-search challenge disguised as a combination puzzle. At first glance, it looks like a simple sequence of dial rotations. But once you examine the rules—restricted moves, forbidden states, and the need to minimize the number of rotations—you quickly realize this problem is fundamentally about exploring a state space efficiently.

This is a prime example of why breadth-first search (BFS) is invaluable in interview settings.

Problem

You are given a lock represented by a four-digit string, such as “0000”. Each of the four dials can rotate forward or backward, cycling digits 0–9.

Your goal is to reach a target combination by rotating the dials, but there’s a catch:

• Certain combinations are deadends, meaning the lock will freeze if it ever reaches one.
• From any current combination, you can generate up to eight neighbors by rotating one digit up or down.
• You must find the minimum number of moves needed to reach the target from “0000”.
• If it is impossible, return -1.

Example

Input:

deadends = ["0201","0101","0102","1212","2002"]

target = "0202"

Output:

6

Explanation:

Using BFS, the fewest moves from “0000” to “0202“—while avoiding all deadends—takes exactly six rotations.

Another example:

Input:

deadends = ["8888"]

target = "0009"

Output:

1

Simply rotate the last digit forward: “0000” → “0009“.

Solution

This problem is essentially asking for the shortest path in an implicit graph:

• Each node is a 4-digit combination.
• Each edge represents a valid dial rotation (one step).
• Deadends are nodes you cannot enter.
• You are asked for the fewest edges needed to reach the target.

This setup makes Breadth-First Search (BFS) the perfect solution.

Key idea

From “0000”, BFS explores all reachable combinations in expanding layers:

• Depth 0: “0000“
• Depth 1: all one-move combinations
• Depth 2: all two-move combinations
  …and so on.

Because BFS explores in order of increasing depth, the first time you encounter the target, you are guaranteed the shortest number of moves.

Why BFS works best

• The search space is bounded: exactly 10⁴ = 10000 possible combinations.
• Each state has at most eight neighbors.
• BFS ensures we never revisit states due to a visited set, preventing infinite loops.
• BFS naturally computes the minimum number of moves.

Handling deadends

You should mark all deadend combinations as visited before starting. That way, BFS will never enqueue them.

If “0000” itself is a deadend, the answer is immediately -1.

Algorithm outline

1. Convert deadends into a set for \( O(1) \) lookups.
2. If “0000” is in the deadend set, return -1.
3. Initialize a queue for BFS starting from “0000“, and a visited set.
4. For each state popped from the queue:
   • If it equals the target, return the current depth.
   • Otherwise, generate all eight possible neighbors by rotating each digit up or down.
   • Add each valid, unvisited neighbor to the queue.
5. If BFS finishes without finding the target, return -1.

Generating neighbors

For a digit d at index i, the two neighbors are:

• (d + 1) % 10
• (d - 1 + 10) % 10

Apply this transformation to each of the four positions.

Sample implementation (Python)

Alternative approach: bidirectional BFS

You can optimize further with bidirectional BFS:

• One search starts from “0000“.
• The other starts from the target.
• They meet in the middle, often reducing search time dramatically.

This isn’t required for correctness, but it’s a great enhancement to discuss in interviews.

Interview insight

The Open the Lock problem tests several foundational skills:

• Mapping puzzles to graph search problems
• Choosing BFS for shortest-path searches in unweighted graphs
• Efficiently generating neighbors
• Managing visited states and forbidden states

Once you recognize the graph structure, the problem becomes straightforward—but that recognition is exactly what interviewers want to see.