Open the Lock - Video Solutions

Problem Overview: You start with a 4‑wheel lock showing "0000". Each move rotates one wheel up or down by one digit. Some combinations are deadends and cannot be visited. The goal is to reach a target combination using the minimum number of moves.

The lock state space is small: each wheel has 10 digits, so there are at most 10^4 possible combinations. Each state can generate up to 8 neighbors (increment or decrement each of the four wheels). The problem becomes a shortest‑path search on an implicit graph where nodes are lock combinations and edges represent valid rotations.

Approach 1: Breadth‑First Search (BFS) (Time: O(10^4), Space: O(10^4))

Model the lock as a graph and run Breadth-First Search starting from "0000". BFS explores all combinations reachable in 1 move, then 2 moves, and so on, guaranteeing the first time you reach the target is the shortest path. Store deadends in a hash table for O(1) checks and maintain a visited set to avoid revisiting combinations.

For each state, generate its 8 neighbors by rotating each wheel forward or backward. For example, rotating the first wheel of "1234" produces "0234" and "2234". Push valid neighbors into the queue and track the number of levels processed. BFS works well here because the graph is small and unweighted, making level‑order traversal an exact match for the minimum move requirement.

Approach 2: Bidirectional Breadth‑First Search (Time: O(10^4), Space: O(10^4))

Bidirectional BFS improves search efficiency by expanding from both the start ("0000") and the target simultaneously. Instead of exploring the entire frontier from one side, maintain two frontiers and always expand the smaller one. When the frontiers intersect, the shortest path is found.

This approach drastically reduces the number of explored states because each search covers roughly half the distance. In a graph with branching factor b and depth d, regular BFS explores about b^d nodes, while bidirectional BFS explores roughly b^(d/2) from each side. Deadends and visited states are still tracked using a set, and neighbor generation follows the same wheel rotation logic as the standard BFS approach.

Recommended for interviews: Start with the standard BFS solution. It directly models the problem as a shortest‑path search on an unweighted graph and clearly demonstrates your understanding of graph traversal and state exploration. Once that solution is clear, mentioning bidirectional BFS shows deeper optimization awareness and familiarity with advanced search techniques used in graph problems involving symmetric start and target states.