752. Open the Lock


Problem Description

In this problem, we have a lock that is represented by 4 circular wheels, each with digits from 0 to 9. The lock opens when the wheels show a specific combination of numbers called the target. We can turn one wheel at a time which will either increase or decrease the digit on the wheel by 1. The twist here is that there are certain combinations which are "deadends", meaning if we reach any of these combinations, the lock gets stuck and we can no longer manipulate it. Our goal is to find the minimum number of moves required to reach the target combination from the starting position '0000', while avoiding these deadends. If it's not possible to reach the target, we should return -1.

The challenge involves figuring out the shortest path to the target without hitting any deadends. It's like navigating a maze where each wheel turn changes your path slightly and you're trying to find the quickest route to the exit (target combination).

Intuition

To solve this problem, we can use the Breadth-First Search (BFS) algorithm. BFS is an ideal choice for finding the shortest path on an unweighted graph or in our case, the fewest number of moves to reach the target. Each state of the lock can be treated as a node in the graph and each possible turn of a wheel can be considered as an edge to a new node.

Here's our plan of attack:

  1. BFS: We will perform a bidirectional BFS, starting from both the initial '0000' state and the target state. Bidirectional BFS can be more efficient than standard BFS as it may reduce the search space, because the searches from both ends will meet in the middle.

  2. Next States Generation: For each state (lock combination), we need to consider all possible "next" states. We can achieve this by writing a function to turn each wheel forward or backward, generating up to 8 new combinations from each state.

  3. Deadends Avoidance: Before we even start searching, we should put all deadends in a set for quick access and to make sure we never enqueue these states in our BFS.

  4. Searching for Connection: During the BFS, we explore nodes level by level, alternating expansion between the start and target searching blocks. If we encounter a node/state that's already been reached from the other direction, we have found a connection, and we can calculate the total steps taken.

  5. Handling Corner Cases: We check if the target is the initial lock state '0000', in which case we return 0 as no moves are required. Similarly, if '0000' is in the deadends, we return -1 because it's impossible to start.

Through these steps, the provided solution effectively finds the shortest path — that is, the minimum number of moves — to unlock the lock or determines that it's not possible.

Learn more about Breadth-First Search patterns.

Solution Approach

The solution follows the BFS strategy described in the intuition:

  1. Deadend Preprocessing: Store all the deadends into a set called s for O(1) access time. This is important to quickly check whether a generated combination is a deadend or not, allowing us to skip it if necessary.

  2. Handling Base Cases: If the target is the same as the initial state (i.e., '0000'), we return 0 because no moves are needed. If '0000' is in the deadends set, we return -1 as we cannot start.

  3. Bidirectional BFS Initialization: Two hash maps m1 and m2 are initialized to represent the BFS layers starting from '0000' and target, respectively. Each map holds states as keys and the number of moves to reach them as values. Two double-ended queues q1 and q2 are also initiated to hold the states for processing.

  4. BFS with Two Queues: The core of the BFS occurs with two queues, where the method extend attempts to add adjacent states to the smaller queue, to ensure we always expand the search frontier with fewer nodes. This is a performance optimization that leverages the bidirectional search.

  5. Generating Adjacent States: The next method is important for the state space exploration. For each of the four wheels in a given state, it generates 2 adjacent states: one by increasing the digit and one by decreasing it while handling the wrap-around from '9' to '0' and '0' to '9'.

  6. Searching and Building Layers: Each expansion with the extend method takes a state p from the queue, checks all adjacent states generated by next(p) if any is not a deadend or already visited. If it finds the state in the opposite map (indicating that the two BFS meet), it returns the total move count. Otherwise, it updates the map with the new move count and enqueues the state.

  7. Reaching the Target: The algorithm continues this process until the queues are empty or until the searches from both ends meet - at which point it returns the total count of steps taken.

  8. Returning the Result: If the BFS does not find a connection, it signifies that the target cannot be reached without hitting a deadend, and therefore, it returns -1.

This is a clever use of bidirectional BFS to reduce the search space and improve efficiency, especially when the target is far from the initial state. The decision to move from one side is chosen based on the size of the queues, making the search strategy dynamic and adaptive to the states that have been already explored.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement priority queue?

Example Walkthrough

Let's consider a simplified example where the lock has only two wheels (for brevity) with digits from 0 to 9 and the following deadends: ["01", "10", "12"]. The target combination is "11".

Here is a step-by-step walkthrough using the solution approach:

  1. Deadend Preprocessing: First, we add all the deadends into a set s for quick look-up. If we attempt to generate any of these combinations, we will know instantly and avoid them.

  2. Handling Base Cases: The initial state is "00". Since this isn't a deadend and it isn't the target, we continue. The target "11" isn't the initial state, so we don't return 0. Also, "00" is not in the deadends set, so we don't return -1.

  3. Bidirectional BFS Initialization: We create two hash maps m1 and m2. m1 starts with {"00": 0} and m2 with {"11": 0} indicating the initial state and target each require 0 moves to reach from themselves. Also, two queues q1 and q2 are initialized containing "00" and "11", respectively.

  4. BFS with Two Queues: We alternate between the queues, starting with q1 (since both are the same size initially). In this example, q1 has fewer nodes most of the time.

  5. Generating Adjacent States: The next method generates new states by incrementing or decrementing the digits of the current state avoiding rolling over a deadend. So from "00" it generates "01" and "09" for the first wheel and "10" and "90" for the second wheel.

  6. Searching and Building Layers: However, since "01" and "10" are deadends, they are not added to the search queue. "09" and "90" would be added to m1.

  7. Reaching the Target: Since one of the generated states "90" upon decrement of the first wheel will convert to "80" which is not in m2 and is not a deadend, it will be added to q1. Similarly, from the target side, "11" will generate "21" and "01" for the first wheel and "10" and "12" for the second wheel. "01" and "10" are deadends and "12" is also a deadend, so only "21" is added to m2 and subsequently "20" and "22" from "21" which leads to "20" being enqueued. Notably, "20" is one step away from "00" and also one step away from "21" which was derived from the target "11".

Since "90" from q1 and "20" from q2 are adjacent on the lock (you can get from one to the other by a single move on the second wheel), when we increment the second wheel of "20", we find "20" in m1, indicating that the searches have met. m1['20'] contains the number of steps to get from "00" to "20" (which is 1 move), and m2['20'] contains the number of steps from "11" to "20" (also 1 move). Thus, the minimum number of moves to get to "11" from "00" without hitting a deadend is the sum of these two, which is 1 + 1 = 2.

  1. Returning the Result: Since we've found a connection, we return the total count of moves which is 2. If no connection were found and the queues were exhausted, we would return -1 to signify the target is not reachable without hitting a deadend.

Solution Implementation

1from collections import deque
2from typing import List
3
4class Solution:
5    def openLock(self, deadends: List[str], target: str) -> int:
6        # Function to generate the next possible combinations from current state
7        def get_next_states(state):
8            next_states = []
9            state_digits = list(state)
10            for i in range(4):
11                original_digit = state_digits[i]
12                # Decrement the digit (with wrap-around)
13                state_digits[i] = '9' if original_digit == '0' else str(int(original_digit) - 1)
14                next_states.append(''.join(state_digits))
15                # Increment the digit (with wrap-around)
16                state_digits[i] = '0' if original_digit == '9' else str(int(original_digit) + 1)
17                next_states.append(''.join(state_digits))
18                # Restore original digit for the next iteration
19                state_digits[i] = original_digit
20            return next_states
21
22        # Function to perform one step of bidirectional BFS
23        def extend(frontier, opposite_frontier, queue):
24            for _ in range(len(queue)):
25                current_state = queue.popleft()
26                current_step = frontier[current_state]
27                for next_state in get_next_states(current_state):
28                    if next_state in deadend_set or next_state in frontier:
29                        continue
30                    if next_state in opposite_frontier:
31                        return current_step + 1 + opposite_frontier[next_state]
32                    frontier[next_state] = current_step + 1
33                    queue.append(next_state)
34            return -1
35
36        # Main BFS function used for bidirectional search
37        def bidirectional_bfs():
38            start_frontier = {"0000": 0}  # Map of seen combinations starting from "0000"
39            target_frontier = {target: 0}  # Map of seen combinations starting from the target
40            start_queue = deque(['0000'])   # Queue for the BFS from "0000"
41            target_queue = deque([target])  # Queue for the BFS from the target
42
43            while start_queue and target_queue:
44                # Alternate between expanding from the start and target
45                result = extend(start_frontier, target_frontier, start_queue) if len(start_queue) <= len(target_queue) else extend(target_frontier, start_frontier, target_queue)
46                if result != -1:
47                    return result
48            return -1  # No solution found
49
50        # If the target is "0000", it's already unlocked
51        if target == '0000':
52            return 0
53        # Initialize dead end states in a set for quick lookup
54        deadend_set = set(deadends)
55        # If "0000" is in dead ends, we cannot start
56        if '0000' in deadend_set:
57            return -1
58        # Perform bidirectional BFS
59        return bidirectional_bfs()
60
61# Example usage:
62# solution = Solution()
63# min_turns = solution.openLock(["0201","0101","0102","1212","2002"], "0202")
64# print(min_turns) # This would output the minimum number of turns required to open the lock.
65
1class Solution {
2    private String startCombination; // Start combination for the lock
3    private String targetCombination; // Target combination to unlock
4    private Set<String> deadEnds = new HashSet<>(); // Set to store deadends
5
6    // Method to find the minimum number of moves to open the lock
7    public int openLock(String[] deadends, String target) {
8        startCombination = "0000";
9        this.targetCombination = target;
10
11        // Add all deadends to the set
12        Collections.addAll(this.deadEnds, deadends);
13      
14        // If the starting point is a deadend, we cannot proceed
15        if (this.deadEnds.contains(startCombination)) {
16            return -1;
17        }
18      
19        // If target is startCombination return 0 as no steps required
20        if (target.equals(startCombination)) {
21            return 0;
22        }
23
24        // Use bidirectional BFS to find the shortest path
25        return bidirectionalBfs();
26    }
27
28    // Helper method to perform bidirectional BFS search on the lock combinations
29    private int bidirectionalBfs() {
30        Map<String, Integer> visitedFromStart = new HashMap<>(); // Record steps from start
31        Map<String, Integer> visitedFromTarget = new HashMap<>(); // Record steps from target
32        Deque<String> queueFromStart = new ArrayDeque<>(); // Queue for BFS from start
33        Deque<String> queueFromTarget = new ArrayDeque<>(); // Queue for BFS from target
34
35        // Initialize the BFS from both ends
36        visitedFromStart.put(startCombination, 0);
37        visitedFromTarget.put(targetCombination, 0);
38        queueFromStart.offer(startCombination);
39        queueFromTarget.offer(targetCombination);
40
41        while (!queueFromStart.isEmpty() && !queueFromTarget.isEmpty()) {
42            // Always extend the smaller queue to optimize performance
43            int turns = queueFromStart.size() <= queueFromTarget.size() ?
44                        extendQueue(visitedFromStart, visitedFromTarget, queueFromStart) :
45                        extendQueue(visitedFromTarget, visitedFromStart, queueFromTarget);
46          
47            // If turns not equals to -1, a solution has been found
48            if (turns != -1) {
49                return turns;
50            }
51        }
52        return -1; // If no solution is found
53    }
54
55    // Expand the current level of the BFS search and check for intersections
56    private int extendQueue(Map<String, Integer> currentVisited, Map<String, Integer> oppositeVisited, Deque<String> currentQueue) {
57        int currentSize = currentQueue.size();
58        for (int i = 0; i < currentSize; ++i) {
59            String currentCombination = currentQueue.poll();
60            int currentStepCount = currentVisited.get(currentCombination);
61          
62            // Evaluate next possible combinations
63            for (String nextCombination : getNextCombinations(currentCombination)) {
64                // Skip if visited or is a dead end
65                if (currentVisited.containsKey(nextCombination) || deadEnds.contains(nextCombination)) {
66                    continue;
67                }
68
69                // If this combination has been reached from the opposite direction, return the total move count
70                if (oppositeVisited.containsKey(nextCombination)) {
71                    return currentStepCount + 1 + oppositeVisited.get(nextCombination);
72                }
73              
74                // Record the step count and add the new combination to the queue
75                currentVisited.put(nextCombination, currentStepCount + 1);
76                currentQueue.offer(nextCombination);
77            }
78        }
79        return -1;
80    }
81
82    // Generate all next possible lock combinations from a given combination
83    private List<String> getNextCombinations(String combination) {
84        List<String> nextCombinations = new ArrayList<>();
85        char[] chars = combination.toCharArray();
86      
87        for (int i = 0; i < 4; ++i) {
88            char originalChar = chars[i];
89          
90            // Turn the wheel one step forward
91            chars[i] = originalChar == '9' ? '0' : (char) (originalChar + 1);
92            nextCombinations.add(new String(chars));
93          
94            // Turn the wheel one step backwards
95            chars[i] = originalChar == '0' ? '9' : (char) (originalChar - 1);
96            nextCombinations.add(new String(chars));
97          
98            // Restore the original state for the next iteration
99            chars[i] = originalChar;
100        }
101      
102        return nextCombinations;
103    }
104}
105
1#include <vector>
2#include <string>
3#include <unordered_set>
4#include <unordered_map>
5#include <queue>
6using namespace std;
7
8class Solution {
9public:
10    unordered_set<string> deadendsSet;
11    string start;
12    string target;
13
14    // Tries to unlock the lock by turning the wheels,
15    // avoiding deadends and finding the shortest path to the target combination.
16    int openLock(vector<string>& deadends, string target) {
17        if (target == "0000") return 0;
18      
19        // Populating the deadends set for quick lookups.
20        for (const auto& d : deadends) deadendsSet.insert(d);
21        if (deadendsSet.count("0000")) return -1; // The start point is a deadend.
22      
23        this->start = "0000";
24        this->target = target;
25      
26        // Perform a bidirectional BFS to find the shortest path.
27        return bidirectionalBFS();
28    }
29
30    // Bidirectional BFS to find the shortest path to unlock the lock.
31    int bidirectionalBFS() {
32        unordered_map<string, int> m1; // Maps from string to minimum steps needed from start.
33        unordered_map<string, int> m2; // Maps from string to minimum steps needed from target.
34      
35        m1[start] = 0; // Initialize start
36        m2[target] = 0; // Initialize target
37      
38        queue<string> q1{{start}};
39        queue<string> q2{{target}};
40      
41        while (!q1.empty() && !q2.empty()) {
42            // Choose the queue with fewer elements to extend.
43            int t = (q1.size() <= q2.size()) ? extend(m1, m2, q1) : extend(m2, m1, q2);
44            if (t != -1) return t; // If a connection is found, return the number of steps.
45        }
46        return -1; // If no connection was found, return -1 indicating the lock cannot be unlocked.
47    }
48
49    // Extends the search from one queue, using the other queue to check for a meeting point.
50    int extend(unordered_map<string, int>& visitedFromOneSide, 
51               unordered_map<string, int>& visitedFromOtherSide,
52               queue<string>& queueToExtend) {
53        for (int n = queueToExtend.size(); n > 0; --n) {
54            string currentPosition = queueToExtend.front();
55            int step = visitedFromOneSide[currentPosition];
56            queueToExtend.pop();
57          
58            for (const string& nextPosition : getNextPositions(currentPosition)) {
59                if (deadendsSet.count(nextPosition) || visitedFromOneSide.count(nextPosition)) continue;
60                if (visitedFromOtherSide.count(nextPosition)) {
61                    // If we find the current nextPosition in the other side's visited map,
62                    // we found the shortest path.
63                    return step + 1 + visitedFromOtherSide[nextPosition];
64                }
65              
66                visitedFromOneSide[nextPosition] = step + 1; // Update the step count for the next position.
67                queueToExtend.push(nextPosition);
68            }
69        }
70        return -1;
71    }
72
73    // Generates all possible combinations that can be reached from the current state in one move.
74    vector<string> getNextPositions(string& currentPosition) {
75        vector<string> possibleNextPositions;
76        for (int i = 0; i < 4; ++i) {
77            char originalChar = currentPosition[i];
78
79            // Turn wheel down
80            currentPosition[i] = originalChar == '0' ? '9' : (char) (originalChar - 1);
81            possibleNextPositions.push_back(currentPosition);
82
83            // Turn wheel up
84            currentPosition[i] = originalChar == '9' ? '0' : (char) (originalChar + 1);
85            possibleNextPositions.push_back(currentPosition);
86
87            // Reset the character to the original one
88            currentPosition[i] = originalChar;
89        }
90        return possibleNextPositions;
91    }
92};
93
1// Imports go here in TypeScript, but these are C++ includes
2// and not applicable in TypeScript.
3
4// Defining the global variables for deadends, start, and target.
5let deadendsSet: Set<string> = new Set();
6let start: string = "0000";
7let target: string;
8
9// Tries to unlock the lock by turning the wheels,
10// avoiding deadends and finding the shortest path to the target combination.
11function openLock(deadends: string[], target: string): number {
12    if (target === "0000") return 0;
13
14    // Populating the deadends set for quick lookups.
15    deadendsSet = new Set(deadends);
16    if (deadendsSet.has("0000")) return -1; // The start point is a deadend.
17
18    // Set the global target for use in other functions.
19    target = target;
20
21    // Perform a bidirectional BFS to find the shortest path.
22    return bidirectionalBFS();
23}
24
25// Bidirectional BFS to find the shortest path to unlock the lock.
26function bidirectionalBFS(): number {
27    let m1: Map<string, number> = new Map(); // Maps from string to minimum steps needed from start.
28    let m2: Map<string, number> = new Map(); // Maps from string to minimum steps needed from target.
29
30    m1.set(start, 0); // Initialize start
31    m2.set(target, 0); // Initialize target
32
33    let q1: string[] = [start];
34    let q2: string[] = [target];
35
36    while (q1.length > 0 && q2.length > 0) {
37        // Choose the array with fewer elements to extend.
38        let steps = (q1.length <= q2.length) ? extend(m1, m2, q1) : extend(m2, m1, q2);
39        if (steps !== -1) return steps; // If a connection is found, return the number of steps.
40    }
41    return -1; // If no connection was found, return -1 indicating the lock cannot be unlocked.
42}
43
44// Extends the search from one queue, using the other queue to check for a meeting point.
45function extend(
46    visitedFromOneSide: Map<string, number>,
47    visitedFromOtherSide: Map<string, number>,
48    queueToExtend: string[]
49): number {
50    for (let i = queueToExtend.length - 1; i >= 0; i--) {
51        let currentPosition = queueToExtend.shift()!;
52        let step = visitedFromOneSide.get(currentPosition)!;
53
54        for (const nextPosition of getNextPositions(currentPosition)) {
55            if (deadendsSet.has(nextPosition) || visitedFromOneSide.has(nextPosition)) continue;
56          
57            if (visitedFromOtherSide.has(nextPosition)) {
58                // If we find the current nextPosition in the other side's visited map,
59                // we found the shortest path.
60                return step + 1 + visitedFromOtherSide.get(nextPosition)!;
61            }
62
63            visitedFromOneSide.set(nextPosition, step + 1); // Update the step count for the next position.
64            queueToExtend.push(nextPosition);
65        }
66    }
67    return -1;
68}
69
70// Generates all possible combinations that can be reached from the current state in one move.
71function getNextPositions(currentPosition: string): string[] {
72    let possibleNextPositions: string[] = [];
73    for (let i = 0; i < 4; ++i) {
74        let originalChar = currentPosition[i];
75
76        // Using charCodeAt to get the numeric ASCII value and String.fromCharCode to return to a string character after incrementing/decrementing.
77        // Turn wheel down
78        currentPosition =
79            currentPosition.substring(0, i) +
80            (originalChar === '0' ? '9' : String.fromCharCode(originalChar.charCodeAt(0) - 1)) +
81            currentPosition.substring(i + 1);
82        possibleNextPositions.push(currentPosition);
83
84        // Turn wheel up
85        currentPosition =
86            currentPosition.substring(0, i) +
87            (originalChar === '9' ? '0' : String.fromCharCode(originalChar.charCodeAt(0) + 1)) +
88            currentPosition.substring(i + 1);
89        possibleNextPositions.push(currentPosition);
90
91        // The current character is left unchanged because it's always overwritten in this implementation.
92    }
93    return possibleNextPositions;
94}
95

Time and Space Complexity

The provided Python code implements a bidirectional breadth-first search algorithm to solve the problem of finding the minimum number of moves required to open a lock represented by a 4-digit combination, given a list of "deadends" (combinations that should not be used) and a target combination.

Time Complexity

The time complexity of the code is primarily determined by the breadth-first search (BFS), which in this case, is bidirectional.

  • The BFS explores the state space that consists of all possible combinations of the 4 digits. Since each digit can be between '0' to '9', there are 10^4 possible states.
  • In each step of BFS, we can proceed to 8 different states from the current state (each digit can be turned one step forward or backward), but we may not visit any state more than once, except when states meet from the two searching directions.
  • In the bidirectional BFS, the search stops when the two searches meet. This meeting point is generally expected to be around the middle layers of the search space if there is a path from the start to the target. Therefore, compared to regular BFS, the search space explored is significantly reduced.
  • Since the size of the queue in each BFS direction is doubled for each layer (in the worst case), the maximum number of layers needed for both queues to meet is approximately log_2(10^4), which simplifies to log_2(10) * 4.

Considering the factors above, the time complexity is O(b^d) where b is the branching factor (in this case, 8, for the 8 possible states we can go to from any given state), and d is the effective depth of the search space. Due to the bidirectionality of the BFS, d is effectively halved, resulting in a time complexity of O(8^(log_2(10^4)/2)) or simplified, O(8^(2)), which is O(64) for any states reachable from the start before the search meets another impediment such as a deadend.

Space Complexity

The space complexity is dictated by the storage required for the visited states and the queues holding the states to be processed.

  • Each state is stored with an integer value representing the steps taken to reach it, both from the initial state ('0000') and from the target state.
  • In the worst case, we might need to store all the 10^4 possible states if they are not in deadends.
  • There are two hash maps storing the states from both the start and the end of the search, along with two queues that are used for the search fronts.
  • The largest the queues can get is the maximum branching at that particular layer of the BFS.

Thus, the space complexity is O(2*10^4) for the hash maps plus the space required for the queues. Since the size of the queues is significantly smaller than the map size (because we stop once the two searches meet), the dominant term in the space complexity is O(2*10^4). However, in a practical scenario, the space complexity may be less than this because not all states will be stored if the search ends earlier or many states are deadends.

In summary, the time complexity is O(64), and the space complexity is O(2*10^4) for the given lock opening problem.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄