752. Open the Lock
Problem Description
You have a combination lock with 4 circular wheels, where each wheel can display digits from '0'
to '9'
. The wheels can rotate in both directions and wrap around - meaning you can turn '9'
to '0'
or '0'
to '9'
. In each move, you can turn exactly one wheel by one position (either forward or backward).
The lock starts at the initial position '0000'
. You need to reach a given target
combination to unlock it.
However, there are certain combinations called deadends
that will cause the lock to jam. If the lock ever displays any of these deadend combinations, it becomes stuck and cannot be turned further.
Your task is to find the minimum number of moves required to change the lock from '0000'
to the target
combination without ever landing on a deadend. If it's impossible to reach the target (either because the starting position is a deadend or all paths to the target go through deadends), return -1
.
For example:
- From
'0000'
, you could move to'1000'
,'9000'
,'0100'
,'0900'
,'0010'
,'0090'
,'0001'
, or'0009'
in one move - If
target = '0202'
and there are no deadends, you would need at least 4 moves (turning the second wheel twice and the fourth wheel twice) - If
'0000'
itself is in the deadends list, it's impossible to start, so return-1
Flowchart Walkthrough
First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- Yes: This problem can be modeled as a graph where each lock combination (like '0000', '0001', etc.) is a node, and edges connect combinations that differ by one wheel turn. We need to find the shortest path from '0000' to the target.
Is it a tree?
- No: The graph is not a tree because multiple paths can lead to the same combination, and there can be cycles (you can return to a previous combination).
Is the problem related to directed acyclic graphs?
- No: The graph has cycles (you can go from '0000' to '1000' and back to '0000').
Is the problem related to shortest paths?
- Yes: We need to find the minimum number of moves (shortest path) from the starting combination '0000' to the target combination.
Is the graph Weighted?
- No: Each move (edge) has the same cost of 1. All edges have equal weight since each represents exactly one wheel turn.
BFS
- Yes: Since we have an unweighted graph and need the shortest path, BFS is the optimal choice.
Conclusion: The flowchart correctly leads us to use BFS (Breadth-First Search) for this problem. BFS is ideal here because:
- We're exploring an implicit graph of lock combinations
- All moves have equal cost (unweighted edges)
- We need the minimum number of moves (shortest path)
- BFS guarantees finding the shortest path in unweighted graphs
Intuition
Think of this problem as navigating through a maze where each position in the maze is a 4-digit combination. You start at '0000'
and want to reach your target combination, but some positions in the maze are blocked (the deadends).
The key insight is that from any combination, you can move to exactly 8 neighboring combinations - by turning each of the 4 wheels either forward or backward by one position. For example, from '0000'
, you can reach '1000'
, '9000'
, '0100'
, '0900'
, '0010'
, '0090'
, '0001'
, or '0009'
.
Since each move changes exactly one wheel by one position, every move has the same "cost" of 1. This transforms our problem into finding the shortest path in an unweighted graph, where BFS naturally gives us the optimal solution.
Why BFS works perfectly here:
-
Level-by-level exploration: BFS explores all combinations reachable in 1 move, then 2 moves, then 3 moves, and so on. The first time we encounter the target, we've found it using the minimum number of moves.
-
Avoiding revisits: We need to track visited combinations to avoid going in circles. Once we've reached a combination with
n
moves, there's no point reaching it again with more moves. -
Handling deadends: We treat deadends as pre-visited nodes - we simply never explore them. If
'0000'
itself is a deadend, we can't even start, so we return-1
.
The algorithm essentially performs a breadth-first search starting from '0000'
, exploring all valid neighboring combinations level by level, until we either find the target (return the number of moves) or exhaust all possibilities (return -1
).
Learn more about Breadth-First Search patterns.
Solution Approach
The implementation uses BFS with a queue to explore combinations level by level. Let's walk through the key components:
1. Generating Neighbors
The next(s)
function generates all 8 possible combinations reachable from the current state:
- For each of the 4 wheels (positions 0-3)
- Try turning it backward:
'0'
β'9'
, or decrement by 1 - Try turning it forward:
'9'
β'0'
, or increment by 1 - This gives us 4 wheels Γ 2 directions = 8 neighbors
2. Initial Setup
- Check if target is already
'0000'
- return 0 immediately - Convert deadends to a set
s
for O(1) lookup - Check if
'0000'
is a deadend - return -1 if we can't start - Initialize queue with
'0000'
and add it to visited set
3. BFS Algorithm
while q:
ans += 1 # Increment level/distance
for _ in range(len(q)): # Process all nodes at current level
p = q.popleft()
for t in next(p): # Check all 8 neighbors
if t == target:
return ans # Found target at this level
if t not in s: # Not visited and not a deadend
q.append(t)
s.add(t) # Mark as visited
Key Data Structures:
- Queue (
deque
): Enables efficient FIFO operations for BFS - Set (
s
): Stores both deadends and visited combinations for O(1) lookup - String manipulation: Each combination is stored as a 4-character string
Why This Works:
- The level-by-level processing ensures we find the shortest path
- The visited set prevents revisiting combinations (avoiding infinite loops)
- Deadends are pre-added to the visited set, effectively blocking those paths
- The first time we encounter the target, we've found the minimum number of moves
Time Complexity: O(10^4 Γ 8) = O(80,000) in worst case, as there are 10^4 possible combinations and we might need to explore most of them, with 8 operations per combination.
Space Complexity: O(10^4) for storing visited combinations in the set and queue.
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a concrete example where target = "0202"
and deadends = ["0201", "0101", "0102", "1212", "2002"]
.
Initial State:
- Start:
"0000"
- Target:
"0202"
- Deadends set:
{"0201", "0101", "0102", "1212", "2002"}
Level 0 (0 moves):
- Queue:
["0000"]
- Check if
"0000"
is target? No, continue.
Level 1 (1 move):
- Process
"0000"
and generate 8 neighbors:"1000"
β (valid, add to queue)"9000"
β (valid, add to queue)"0100"
β (valid, add to queue)"0900"
β (valid, add to queue)"0010"
β (valid, add to queue)"0090"
β (valid, add to queue)"0001"
β (valid, add to queue)"0009"
β (valid, add to queue)
- None match target, continue to next level.
Level 2 (2 moves):
- From
"0100"
, we can reach:"0200"
β (valid, not a deadend, add to queue)"0101"
β (deadend, skip)- Other neighbors...
- From other nodes in level 1, generate their neighbors
- Still no target found, continue.
Level 3 (3 moves):
- From
"0200"
, we can reach:"0201"
β (deadend, skip)"0300"
β (valid)"0100"
β (already visited)- Other neighbors...
- Continue processing other nodes at this level.
Level 4 (4 moves):
- Eventually, from some combination (like
"0203"
), we generate:"0202"
β Target found!
- Return 4 moves.
The BFS ensures we explore all combinations reachable in 1 move, then 2 moves, then 3 moves, and so on. When we first encounter "0202"
, we know we've found it using the minimum number of moves (4 in this case). The deadends "0201"
, "0101"
, and "0102"
blocked certain paths, but BFS found an alternative route that avoided them.
Solution Implementation
1class Solution:
2 def openLock(self, deadends: List[str], target: str) -> int:
3 def get_next_states(state: str) -> List[str]:
4 """
5 Generate all possible next states by turning each wheel up or down by 1.
6
7 Args:
8 state: Current 4-digit lock state as string
9
10 Returns:
11 List of all possible next states (8 total: 2 moves per wheel)
12 """
13 next_states = []
14 state_list = list(state)
15
16 for i in range(4):
17 original_digit = state_list[i]
18
19 # Turn wheel down by 1 (wraps from 0 to 9)
20 state_list[i] = '9' if original_digit == '0' else str(int(original_digit) - 1)
21 next_states.append(''.join(state_list))
22
23 # Turn wheel up by 1 (wraps from 9 to 0)
24 state_list[i] = '0' if original_digit == '9' else str(int(original_digit) + 1)
25 next_states.append(''.join(state_list))
26
27 # Restore original digit for next iteration
28 state_list[i] = original_digit
29
30 return next_states
31
32 # Edge case: already at target
33 if target == '0000':
34 return 0
35
36 # Initialize visited set with deadends
37 visited = set(deadends)
38
39 # Edge case: starting position is a deadend
40 if '0000' in visited:
41 return -1
42
43 # BFS initialization
44 queue = deque(['0000'])
45 visited.add('0000')
46 steps = 0
47
48 # BFS to find shortest path
49 while queue:
50 steps += 1
51 # Process all nodes at current level
52 for _ in range(len(queue)):
53 current_state = queue.popleft()
54
55 # Check all possible next states
56 for next_state in get_next_states(current_state):
57 # Found target
58 if next_state == target:
59 return steps
60
61 # Add unvisited valid states to queue
62 if next_state not in visited:
63 queue.append(next_state)
64 visited.add(next_state)
65
66 # Target unreachable
67 return -1
68
1class Solution {
2 /**
3 * Finds the minimum number of turns to open a lock from "0000" to target,
4 * avoiding deadend combinations.
5 *
6 * @param deadends Array of deadend combinations to avoid
7 * @param target The target combination to reach
8 * @return Minimum number of turns, or -1 if impossible
9 */
10 public int openLock(String[] deadends, String target) {
11 // Check if we're already at target
12 if ("0000".equals(target)) {
13 return 0;
14 }
15
16 // Create set of deadends for O(1) lookup
17 Set<String> visitedOrDeadends = new HashSet<>(Arrays.asList(deadends));
18
19 // Check if starting position is a deadend
20 if (visitedOrDeadends.contains("0000")) {
21 return -1;
22 }
23
24 // Initialize BFS queue with starting position
25 Deque<String> queue = new ArrayDeque<>();
26 queue.offer("0000");
27 visitedOrDeadends.add("0000"); // Mark start as visited
28
29 int steps = 0;
30
31 // BFS to find shortest path
32 while (!queue.isEmpty()) {
33 steps++;
34 int currentLevelSize = queue.size();
35
36 // Process all nodes at current level
37 for (int i = 0; i < currentLevelSize; i++) {
38 String currentCombination = queue.poll();
39
40 // Generate all possible next combinations
41 for (String nextCombination : getNextCombinations(currentCombination)) {
42 // Check if we've reached the target
43 if (target.equals(nextCombination)) {
44 return steps;
45 }
46
47 // Add unvisited combinations to queue
48 if (!visitedOrDeadends.contains(nextCombination)) {
49 queue.offer(nextCombination);
50 visitedOrDeadends.add(nextCombination);
51 }
52 }
53 }
54 }
55
56 // Target unreachable
57 return -1;
58 }
59
60 /**
61 * Generates all possible combinations by turning each wheel one step
62 * forward or backward from the current combination.
63 *
64 * @param currentCombination The current 4-digit combination
65 * @return List of all possible next combinations (8 total)
66 */
67 private List<String> getNextCombinations(String currentCombination) {
68 List<String> nextCombinations = new ArrayList<>();
69 char[] digits = currentCombination.toCharArray();
70
71 // For each wheel position
72 for (int wheelIndex = 0; wheelIndex < 4; wheelIndex++) {
73 char originalDigit = digits[wheelIndex];
74
75 // Turn wheel backward (decrease digit)
76 digits[wheelIndex] = originalDigit == '0' ? '9' : (char) (originalDigit - 1);
77 nextCombinations.add(String.valueOf(digits));
78
79 // Turn wheel forward (increase digit)
80 digits[wheelIndex] = originalDigit == '9' ? '0' : (char) (originalDigit + 1);
81 nextCombinations.add(String.valueOf(digits));
82
83 // Restore original digit for next wheel
84 digits[wheelIndex] = originalDigit;
85 }
86
87 return nextCombinations;
88 }
89}
90
1class Solution {
2public:
3 int openLock(vector<string>& deadends, string target) {
4 // Create a set of deadends for O(1) lookup and to track visited states
5 unordered_set<string> visited(deadends.begin(), deadends.end());
6
7 // Check if starting position is a deadend
8 if (visited.count("0000")) {
9 return -1;
10 }
11
12 // Check if we're already at target
13 if (target == "0000") {
14 return 0;
15 }
16
17 // Initialize BFS queue with starting position
18 queue<string> bfsQueue{{"0000"}};
19 visited.insert("0000"); // Mark starting position as visited
20
21 int steps = 0;
22
23 // BFS to find shortest path to target
24 while (!bfsQueue.empty()) {
25 ++steps;
26 int levelSize = bfsQueue.size();
27
28 // Process all nodes at current level
29 for (int i = 0; i < levelSize; ++i) {
30 string currentCombination = bfsQueue.front();
31 bfsQueue.pop();
32
33 // Generate all possible next combinations
34 for (string nextCombination : getNextCombinations(currentCombination)) {
35 // Check if we reached the target
36 if (nextCombination == target) {
37 return steps;
38 }
39
40 // Add unvisited combinations to queue
41 if (!visited.count(nextCombination)) {
42 bfsQueue.push(nextCombination);
43 visited.insert(nextCombination);
44 }
45 }
46 }
47 }
48
49 // Target is unreachable
50 return -1;
51 }
52
53private:
54 // Generate all possible combinations by turning each wheel up or down by 1
55 vector<string> getNextCombinations(string& combination) {
56 vector<string> nextCombinations;
57
58 // Try rotating each of the 4 wheels
59 for (int wheelIndex = 0; wheelIndex < 4; ++wheelIndex) {
60 char originalDigit = combination[wheelIndex];
61
62 // Rotate wheel backward (decrease by 1, wrap from 0 to 9)
63 combination[wheelIndex] = (originalDigit == '0') ? '9' : (char)(originalDigit - 1);
64 nextCombinations.push_back(combination);
65
66 // Rotate wheel forward (increase by 1, wrap from 9 to 0)
67 combination[wheelIndex] = (originalDigit == '9') ? '0' : (char)(originalDigit + 1);
68 nextCombinations.push_back(combination);
69
70 // Restore original digit for next iteration
71 combination[wheelIndex] = originalDigit;
72 }
73
74 return nextCombinations;
75 }
76};
77
1/**
2 * Finds the minimum number of turns to open a lock from "0000" to target,
3 * avoiding deadend combinations using BFS
4 * @param deadends - Array of forbidden combinations
5 * @param target - Target combination to reach
6 * @returns Minimum number of turns, or -1 if impossible
7 */
8function openLock(deadends: string[], target: string): number {
9 // Create visited array for all possible combinations (0000-9999)
10 const visited: boolean[] = Array<boolean>(10000);
11
12 // Initialize BFS queue with starting position [digit1, digit2, digit3, digit4, steps]
13 const queue: number[][] = [[0, 0, 0, 0, 0]];
14
15 // Convert target string to number for comparison
16 const targetNumber: number = Number(target);
17
18 // Mark all deadends as visited to avoid them
19 deadends.forEach((deadend: string) => {
20 visited[Number(deadend)] = true;
21 });
22
23 // BFS traversal
24 for (const [firstDigit, secondDigit, thirdDigit, fourthDigit, steps] of queue) {
25 // Calculate current combination as a number
26 const currentCombination: number = firstDigit * 1000 + secondDigit * 100 +
27 thirdDigit * 10 + fourthDigit;
28
29 // Skip if this combination is already visited or is a deadend
30 if (visited[currentCombination]) {
31 continue;
32 }
33
34 // Mark current combination as visited
35 visited[currentCombination] = true;
36
37 // Check if we reached the target
38 if (currentCombination === targetNumber) {
39 return steps;
40 }
41
42 // Try turning each wheel both forward and backward
43 for (let wheelIndex = 0; wheelIndex < 4; wheelIndex++) {
44 // Create arrays for next states (turning wheel forward and backward)
45 const turnForward: number[] = [firstDigit, secondDigit, thirdDigit, fourthDigit, steps + 1];
46 const turnBackward: number[] = [firstDigit, secondDigit, thirdDigit, fourthDigit, steps + 1];
47
48 // Turn current wheel forward (with wraparound using modulo)
49 // Adding 11 instead of 1 to handle negative numbers properly with modulo
50 turnForward[wheelIndex] = (turnForward[wheelIndex] + 11) % 10;
51
52 // Turn current wheel backward (with wraparound using modulo)
53 // Adding 9 is equivalent to subtracting 1 with modulo 10
54 turnBackward[wheelIndex] = (turnBackward[wheelIndex] + 9) % 10;
55
56 // Add both new states to the queue
57 queue.push(turnBackward, turnForward);
58 }
59 }
60
61 // Target cannot be reached
62 return -1;
63}
64
Time and Space Complexity
Time Complexity: O(10^4 * 4 * 2) = O(10^4)
The algorithm uses BFS to explore all possible lock combinations. In the worst case:
- There are
10^4
possible combinations (4 digits, each ranging from 0-9) - For each combination visited, the
next()
function generates neighbors by:- Iterating through 4 positions
- For each position, creating 2 new combinations (increment and decrement)
- Each string operation inside
next()
takesO(4)
time for joining
- So processing each node takes
O(4 * 2 * 4) = O(32) = O(1)
time - Total time:
O(10^4 * 1) = O(10^4)
Space Complexity: O(10^4)
The space is dominated by:
- The set
s
which stores visited combinations and deadends: up toO(10^4)
entries in worst case - The queue
q
which can contain up toO(10^4)
combinations in worst case - The
next()
function creates temporary lists and strings, but this isO(1)
space per call - Total space:
O(10^4)
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Forgetting to Check if Starting Position is a Deadend
One of the most common mistakes is not checking whether '0000'
itself is in the deadends list before starting the BFS. If the starting position is blocked, the lock is immediately stuck and cannot make any moves.
Incorrect approach:
# Missing the initial deadend check
visited = set(deadends)
queue = deque(['0000'])
visited.add('0000') # This adds '0000' even if it's a deadend!
Correct approach:
visited = set(deadends)
if '0000' in visited: # Check BEFORE adding to queue
return -1
queue = deque(['0000'])
visited.add('0000')
2. Inefficient Level Tracking in BFS
Another pitfall is incrementing the step counter for each node processed rather than for each level. This leads to incorrect distance calculations.
Incorrect approach:
while queue: current = queue.popleft() steps += 1 # Wrong! This increments for every node for next_state in get_next_states(current): if next_state == target: return steps
Correct approach:
while queue:
steps += 1 # Increment once per level
for _ in range(len(queue)): # Process all nodes at current level
current = queue.popleft()
for next_state in get_next_states(current):
if next_state == target:
return steps
3. String Mutation Issues When Generating Neighbors
Python strings are immutable, so attempting to modify them directly won't work. Additionally, forgetting to restore the original digit when generating multiple neighbors can lead to incorrect states.
Incorrect approach:
def get_next_states(state):
next_states = []
for i in range(4):
state[i] = str((int(state[i]) + 1) % 10) # Error: strings are immutable
next_states.append(state)
state[i] = str((int(state[i]) - 1) % 10) # Wrong calculation
next_states.append(state)
Correct approach:
def get_next_states(state):
next_states = []
state_list = list(state) # Convert to mutable list
for i in range(4):
original = state_list[i] # Save original
# Generate both neighbors
state_list[i] = '9' if original == '0' else str(int(original) - 1)
next_states.append(''.join(state_list))
state_list[i] = '0' if original == '9' else str(int(original) + 1)
next_states.append(''.join(state_list))
state_list[i] = original # Restore for next iteration
4. Not Handling the Edge Case Where Target is '0000'
If the target is the starting position itself, the answer should be 0, not going through the entire BFS process.
Solution: Always check this edge case at the beginning:
if target == '0000': return 0
How does merge sort divide the problem into subproblems?
Recommended Readings
https assets algo monster cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell Breadth First Search BFS
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Donβt Miss This!