Facebook Pixel

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:

  1. We're exploring an implicit graph of lock combinations
  2. All moves have equal cost (unweighted edges)
  3. We need the minimum number of moves (shortest path)
  4. BFS guarantees finding the shortest path in unweighted graphs
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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:

  1. 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.

  2. 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.

  3. 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:

  1. The level-by-level processing ensures we find the shortest path
  2. The visited set prevents revisiting combinations (avoiding infinite loops)
  3. Deadends are pre-added to the visited set, effectively blocking those paths
  4. 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 Evaluator

Example 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() takes O(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 to O(10^4) entries in worst case
  • The queue q which can contain up to O(10^4) combinations in worst case
  • The next() function creates temporary lists and strings, but this is O(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
Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

How does merge sort divide the problem into subproblems?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More