Domain 2MediumMEDIUM

Open the Lock

LeetCode problem 752: Open the Lock (medium).

Domain: medium•Updated: 2026-08-31
#Breadth-first Search

Problem Breakdown

We are modeling a lock with four wheels as nodes in an implicit graph where each node represents one of 10410^4 possible combinations (e.g., “0235”). An edge exists between two states if they differ by exactly one wheel rotation. The cost to traverse any edge is 1 move.

Inputs:

  • deadends: A list of strings representing blocked nodes we cannot visit or start from.
  • target: The destination string (e.g., “0202”).
  • Start state: Always "0000".

Outputs:

  • Minimum number of moves to reach target, or -1 if unreachable.

Implicit Constraints & Edge Cases:

  • Start Blocked: If the start position ("0000") is in deadends, we cannot move at all, so return -1 immediately (Example 4).
  • Unreachable Target: The graph might be disconnected due to deadends blocking paths. BFS will exhaust reachable nodes; if target isn’t found, return -1.
  • State Space Size: There are exactly 104=10,00010^4 = 10,000 possible states. This is small enough for a standard BFS without optimization like bidirectional search (though that would be an advanced follow-up).

Intuition

This problem asks for the shortest path in an unweighted graph. A Depth-First Search (DFS) might find a path but not necessarily the minimum number of moves, and it risks infinite loops or missing shorter paths due to backtracking without state tracking. Breadth-First Search (BFS) is required because it explores layer-by-layer from the start node; the first time we encounter target, that distance must be minimal.

Why Brute Force Fails: A naive DFS would explore every permutation until hitting a target or deadend, potentially visiting nodes multiple times and failing to track minimum steps efficiently (O(N!)O(N!) worst case without pruning). BFS ensures each node is visited exactly once in the shortest path context. We must treat deadends as blocked nodes that we never add to our queue or visit set.

Approach

  1. Preprocessing: Convert deadends into a hash set for O(1)O(1) lookup time. Check if start ("0000") is in this set; if so, return -1 immediately. If target equals start, return 0.
  2. BFS Initialization: Use a queue (deque) to store states and track distance level-by-level. Maintain a visited set to prevent cycles and redundant processing of the same state. Add all deadends to this visited/blocked logic implicitly by checking against it before adding neighbors, but strictly speaking, we should treat them as invalid nodes from step 1.
  3. BFS Execution: While the queue is not empty:
    • Iterate through the current level of nodes (to calculate distance correctly).
    • For each node in the queue, generate all possible next states by rotating up or down for each of the 4 wheels. This yields 2×4=82 \times 4 = 8 neighbors per state.
    • If a neighbor is target, return current level + 1.
    • If a neighbor is not in deadends and not visited, add to queue and mark as visited.
  4. Termination: If the queue empties without finding target, it’s unreachable; return -1.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the total number of possible lock combinations (104=10,00010^4 = 10,000). In BFS, we visit each state at most once. Generating neighbors takes constant time (8 operations per node). Thus, roughly proportional to the size of the graph space plus deadends processing for initial set construction.
  • Space Complexity: O(N)O(N) to store the visited set and the queue in the worst case where we visit half the state space before finding target or exhausting it.

Solution

from collections import deque
from typing import List

def open_the_lock(deadends: List[str], target: str) -> int:
    # Convert deadends to a set for O(1) lookup time
    dead_set = set(deadends)
    
    start_node = "0000"
    
    # Edge case: Start is blocked immediately or already at target
    if start_node in dead_set:
        return -1
    
    if start_node == target:
        return 0
        
    queue = deque([start_node])
    visited = {start_node}
    level = 0
    
    while queue:
        # Process all nodes at the current distance (level)
        size = len(queue)
        
        for _ in range(size):
            curr = queue.popleft()
            
            if curr == target:
                return level
            
            # Generate neighbors by rotating each of 4 wheels up/down
            for i in range(4):
                digit_idx = int(curr[i])
                
                # Rotate Up (+1) and Down (-1), handling wrap-around (0 <-> 9)
                next_digit_up = str((digit_idx + 1) % 10)
                next_digit_down = str((digit_idx - 1 + 10) % 10)
                
                # Construct new state strings efficiently
                neighbor_up = curr[:i] + next_digit_up + curr[i+1:]
                neighbor_down = curr[:i] + next_digit_down + curr[i+1:]
                
                neighbors = [neighbor_up, neighbor_down]
                
                for nxt in neighbors:
                    # Check if valid (not deadend and not visited)
                    if nxt not in dead_set and nxt not in visited:
                        queue.append(nxt)
                        visited.add(nxt)
        
        level += 1
        
    return -1

# Example usage matching the prompt's structure logic implicitly handled above

Edge Cases Handled

  • Start is a Deadend: The code checks if start_node in dead_set at initialization and returns -1. This handles Example 4.
  • Target equals Start: Explicitly checked to return 0 immediately, avoiding unnecessary BFS steps.
  • Unreachable Target: If the queue empties (all reachable nodes visited) without hitting target, it returns -1, covering cases where deadends isolate the start from the target.
  • Deadend Duplicates/Ordering: Converting to a set handles duplicates in deadends automatically and ensures order doesn’t affect correctness or performance.