# LeetCode 752: Open the Lock ## Problem Restatement We have a lock with four wheels. Each wheel contains digits from `0` to `9`. The lock starts at: ```python "0000" ``` In one move, we can rotate exactly one wheel by one step. The digits wrap around: ```text 9 -> 0 0 -> 9 ``` Some lock states are deadends. If the lock reaches one of those states, it gets stuck and cannot move anymore. Given a list of `deadends` and a `target`, return the minimum number of moves needed to reach `target` from `"0000"`. If the target cannot be reached, return `-1`. ## Input and Output | Item | Meaning | |---|---| | Input | `deadends`, a list of blocked lock states | | Input | `target`, the lock state we want to reach | | Output | Minimum number of turns | | Impossible case | Return `-1` | Example function shape: ```python def openLock(deadends: list[str], target: str) -> int: ... ``` ## Examples Input: ```python deadends = ["0201", "0101", "0102", "1212", "2002"] target = "0202" ``` Output: ```python 6 ``` One valid path is: ```text 0000 -> 1000 -> 1100 -> 1200 -> 1201 -> 1202 -> 0202 ``` This takes `6` moves. Another possible path may get stuck: ```text 0000 -> 0001 -> 0002 -> 0102 ``` The state `"0102"` is a deadend, so that path cannot continue. Another example: ```python deadends = ["8888"] target = "0009" ``` Output: ```python 1 ``` We can rotate the last wheel backward: ```text 0000 -> 0009 ``` ## First Thought: Try All Move Sequences One direct idea is to try every possible sequence of wheel turns. From each state, there are `8` possible moves: For each of the `4` wheels: 1. turn it forward 2. turn it backward For example, from `"0000"` we can move to: ```text 1000 9000 0100 0900 0010 0090 0001 0009 ``` The problem with raw recursion or depth-first search is that it may follow a long path before trying a shorter one. But we need the minimum number of moves. This is a shortest path problem. ## Key Insight Each lock state is a node in a graph. Each valid one-wheel turn is an edge. All edges have the same cost: `1`. So the problem asks for the shortest path from `"0000"` to `target` in an unweighted graph. Breadth-first search is the natural algorithm for this. BFS explores states by distance: | BFS Level | Meaning | |---:|---| | `0` | States reachable in `0` moves | | `1` | States reachable in `1` move | | `2` | States reachable in `2` moves | | `3` | States reachable in `3` moves | The first time BFS reaches `target`, that distance is the minimum number of moves. ## Generating Neighbor States From one lock state, we generate `8` neighbors. Suppose the state is: ```python "1234" ``` For wheel index `0`, digit `1` can become: ```text 2 0 ``` So we get: ```text 2234 0234 ``` For each digit `d`, the next digit forward is: ```python (d + 1) % 10 ``` The next digit backward is: ```python (d - 1) % 10 ``` The modulo handles wraparound: ```text 9 + 1 -> 0 0 - 1 -> 9 ``` Helper function: ```python def neighbors(state: str) -> list[str]: ans = [] for i in range(4): digit = int(state[i]) for move in (-1, 1): next_digit = (digit + move) % 10 next_state = state[:i] + str(next_digit) + state[i + 1:] ans.append(next_state) return ans ``` ## Algorithm 1. Convert `deadends` into a set for fast lookup. 2. If `"0000"` is a deadend, return `-1`. 3. Start BFS from `"0000"`. 4. Store visited states so we do not process the same state repeatedly. 5. For each BFS level: 1. Pop all states at the current distance. 2. If a state equals `target`, return the distance. 3. Generate its neighbors. 4. Add valid, unvisited, non-deadend neighbors to the queue. 6. If BFS finishes without reaching `target`, return `-1`. ## Correctness We model each lock state as a graph node and each legal wheel turn as an edge. Every edge has cost `1`, because every move turns exactly one wheel by one slot. BFS processes nodes in increasing order of distance from the starting state `"0000"`. At distance `0`, it processes only `"0000"`. At distance `1`, it processes all states reachable in one move. At distance `2`, it processes all states reachable in two moves. This continues level by level. The algorithm never explores a deadend, so every state it uses is valid. The `visited` set ensures each state is processed at most once. Once BFS reaches a state, it has already found the shortest path to that state, because BFS reaches states in increasing distance order. Therefore, when the algorithm first sees `target`, the current distance is the minimum number of moves needed to open the lock. If BFS ends without seeing `target`, then every reachable valid state has been explored. In that case, no valid path exists, so returning `-1` is correct. ## Complexity There are only `10,000` possible lock states, from `"0000"` to `"9999"`. Each state has at most `8` neighbors. | Metric | Value | Why | |---|---|---| | Time | `O(10000 * 8)` | Each state is processed once, with up to `8` neighbors | | Space | `O(10000)` | Queue and visited set may store many states | Since `10000` is fixed for this problem, the running time is effectively constant with respect to normal input size. ## Implementation ```python from collections import deque class Solution: def openLock(self, deadends: list[str], target: str) -> int: dead = set(deadends) if "0000" in dead: return -1 queue = deque(["0000"]) visited = {"0000"} moves = 0 while queue: level_size = len(queue) for _ in range(level_size): state = queue.popleft() if state == target: return moves for i in range(4): digit = int(state[i]) for step in (-1, 1): next_digit = (digit + step) % 10 next_state = state[:i] + str(next_digit) + state[i + 1:] if next_state in dead: continue if next_state in visited: continue visited.add(next_state) queue.append(next_state) moves += 1 return -1 ``` ## Code Explanation We first store deadends in a set: ```python dead = set(deadends) ``` This lets us check whether a state is blocked in expected constant time. If the starting state is blocked, there is no move we can make: ```python if "0000" in dead: return -1 ``` Then we start BFS: ```python queue = deque(["0000"]) visited = {"0000"} moves = 0 ``` The queue stores states to process. The `visited` set prevents cycles. The variable `moves` stores the current BFS level. For each level: ```python level_size = len(queue) ``` We process exactly the states that are reachable in `moves` turns. When we pop a state: ```python state = queue.popleft() ``` we check whether it is the target: ```python if state == target: return moves ``` Then we generate all one-move neighbors by trying both directions on each wheel. ```python for i in range(4): digit = int(state[i]) for step in (-1, 1): next_digit = (digit + step) % 10 ``` The modulo makes the wheel circular. So `9 + 1` becomes `0`, and `0 - 1` becomes `9`. We build the next lock state with string slicing: ```python next_state = state[:i] + str(next_digit) + state[i + 1:] ``` Then we skip blocked or already visited states: ```python if next_state in dead: continue if next_state in visited: continue ``` Valid new states are marked visited and added to the queue: ```python visited.add(next_state) queue.append(next_state) ``` After finishing the whole level, we increase the move count: ```python moves += 1 ``` If the queue becomes empty, then all reachable states were checked and the target was not found. ```python return -1 ``` ## Testing ```python def run_tests(): s = Solution() assert s.openLock( ["0201", "0101", "0102", "1212", "2002"], "0202", ) == 6 assert s.openLock( ["8888"], "0009", ) == 1 assert s.openLock( ["8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"], "8888", ) == -1 assert s.openLock( ["0000"], "8888", ) == -1 assert s.openLock( [], "0000", ) == 0 print("all tests passed") run_tests() ``` Test meaning: | Test | Why | |---|---| | Main example | Confirms BFS finds the shortest valid path | | Target one move away | Checks wheel wraparound | | Target surrounded | Confirms impossible case | | Start is deadend | Cannot begin | | Target is start | Requires zero moves |