Skip to main content
Talentd

Open the Lock - Solution & Explanation

MediumArrayHash TableStringBreadth-First Search13 min readAsked at: Amazon, Microsoft, Goldman Sachs +12
Practice this problem

Problem Statement

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

 

Example 1:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation: 
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2:

Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation: We can turn the last wheel in reverse to move from "0000" -> "0009".

Example 3:

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation: We cannot reach the target without getting stuck.

 

Constraints:

  • 1 <= deadends.length <= 500
  • deadends[i].length == 4
  • target.length == 4
  • target will not be in the list deadends.
  • target and deadends[i] consist of digits only.

Approach Overview

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.

Approach 1: Breadth-First Search (BFS)

The problem can be visualized as a graph traversal task, where each state of the lock is a node, and valid moves between states are edges. We use Breadth-First Search (BFS) to explore all possibilities level by level, which ensures that the first time we reach the target state, we have used the minimum number of steps possible.

To implement this approach, initialize a queue for BFS starting with the initial state '0000' and count as 0. Use a set to store deadends and another set for visited states to prevent reprocessing. For each current state, if it is the target, return the count. Otherwise, generate all possible next states by turning each wheel forward and backward, and enqueue all of them that aren't in deadends or the visited set.

The code implements a BFS approach using a queue where each element is a tuple containing the current state and the number of moves taken to reach it. The deadends and visited states are stored in sets to allow quick lookup operations. We iterate through each wheel of the lock, creating new states by incrementing or decrementing the current digit, making sure to wrap around from 9 to 0 or 0 to 9. If a state hasn't been visited or isn't a deadend, it's added to the queue of states to explore next.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(104) due to the maximum number of lock combinations of length 4. Space Complexity: O(104) for storing visited states.

Try this approach in the editor →

Approach 2: Bidirectional Breadth-First Search

To further optimize the BFS approach, a Bidirectional BFS can be employed. We initiate two BFS processes, one from the initial state '0000' and the other from the target state. If they meet at any node, the combined path length gives the answer. This approach can significantly reduce the number of states explored as two searches from opposite ends tend to cover less ground.

The bidirectional BFS starts two searches: one from the initial state '0000' and the other from the target. During each iteration, we always expand the smaller frontier. If they meet, the shortest path is found. By swapping between the starting and ending search direction, we prevent excessive growth of either search frontier. Overall, this reduces the breadth of the search space.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(104) for potential lock combinations of length 4. Space Complexity: O(104) for the visited and active state sets.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Breadth-First Search (BFS)

Time Complexity: O(104) due to the maximum number of lock combinations of length 4. Space Complexity: O(104) for storing visited states.

Bidirectional Breadth-First Search

Time Complexity: O(104) for potential lock combinations of length 4. Space Complexity: O(104) for the visited and active state sets.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Breadth-First Search (BFS)O(10^4)O(10^4)General solution for shortest path in an unweighted state graph
Bidirectional BFSO(10^4) worst case (often much faster)O(10^4)When both start and target states are known and search depth can be reduced

Video Solution

Open the Lock - Leetcode 752 - Python • NeetCode • 57,472 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Open the Lock easy or hard?
Open the Lock is rated Medium on LeetCode. The challenge is recognizing that the lock combinations form a graph and that BFS finds the shortest sequence of moves. Once modeled as a graph problem, the implementation is straightforward.
Open the Lock Python/Java solution
The typical Python and Java solutions implement BFS using a queue. Each iteration pops a lock combination, generates its 8 neighbors by rotating digits, filters deadends using a hash set, and pushes valid states back into the queue until the target combination is reached.
How to solve Open the Lock in O(n)?
Treat each lock combination as a node in a graph and run BFS starting from "0000". Use a queue to explore neighbors created by rotating each wheel up or down and skip combinations listed as deadends. A hash set tracks visited states so each of the at most 10^4 states is processed once.
What is the best approach for Open the Lock?
Breadth-First Search (BFS) is the standard approach because the problem asks for the minimum number of moves in an unweighted graph of lock combinations. BFS guarantees the shortest path by exploring states level by level. Bidirectional BFS is an optimization that reduces the search space by expanding from both the start and target states.
Is Open the Lock asked at Google/Amazon/Meta?
Open the Lock is a common interview problem used by companies such as Amazon and Google to test graph traversal and BFS reasoning. It evaluates how well you model problems as state graphs and apply shortest‑path algorithms.
What data structure is used in Open the Lock?
The main data structures are a queue for BFS traversal and hash sets for deadends and visited states. The queue processes combinations level by level, while the hash set allows constant‑time checks to avoid revisiting invalid or already explored states.
What is the time complexity of Open the Lock?
The time complexity is O(10^4) because there are at most 10,000 possible lock combinations. Each state generates up to 8 neighboring states by rotating one wheel forward or backward. BFS or bidirectional BFS may visit each state at most once.

Ready to solve this problem?

Practice Open the Lock with our built-in code editor and test cases.

Practice on FleetCode
Previous

Reachable Nodes With Restrictions