We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Open the Lock

Number: 753

Difficulty: Medium

Paid? No

Companies: Amazon, Goldman Sachs, TikTok, eBay, Uber, J.P. Morgan

Problem Description

You are given a lock with 4 wheels, each with digits from '0' to '9'. Starting from "0000", you need to reach a given target combination by turning one wheel one slot at a time. However, if you hit any combination from a list of deadends, the lock gets permanently stuck. The task is to determine the minimum number of moves required to reach the target combination, or return -1 if it's not possible.

Key Insights

  • This problem can be modeled as a graph where each node represents a 4-digit combination.
  • Each valid move from one node generates up to 8 neighboring combinations (one for each wheel moving one step forward or backward).
  • Breadth-First Search (BFS) is used to explore the graph level by level, which naturally finds the shortest path.
  • Deadends must be avoided during the traversal.
  • The initial state "0000" must be checked against the deadends.

Space and Time Complexity

Time Complexity: O(10^N) where N is the number of wheels (N = 4 gives 10^4 combinations in worst-case scenario). Space Complexity: O(10^N) due to storing visited states and the queue in BFS.

Solution

We use a Breadth-First Search (BFS) to systematically explore all potential combinations starting from "0000". Each combination represents a state or node in our search space. From each state, we generate all valid next states by incrementing or decrementing each digit (with wraparound behavior). We keep track of combinations that are either deadends or already visited to avoid cycles and unnecessary processing.

Key steps:

  1. Start at "0000" if it is not a deadend.
  2. Use a queue to process one level of combinations at a time, representing the number of moves.
  3. For each combination, generate all possible next moves (neighbors). Skip any that are deadends or that have been visited.
  4. If the target combination is reached, return the level (move count).
  5. If the queue empties without finding the target, return -1.

Code Solutions

# Python implementation
from collections import deque

def openLock(deadends, target):
    dead_set = set(deadends)
    # Early check: if starting point is a deadend, no solution exists.
    if "0000" in dead_set:
        return -1
        
    queue = deque([("0000", 0)])  # (state, moves)
    visited = {"0000"}
    
    # Function to generate neighbors (all possible states from current state)
    def get_neighbors(state):
        neighbors = []
        for i in range(4):
            digit = int(state[i])
            # Two possible moves: increment or decrement with wrap-around
            for move in (-1, 1):
                new_digit = (digit + move) % 10
                new_state = state[:i] + str(new_digit) + state[i+1:]
                neighbors.append(new_state)
        return neighbors
    
    while queue:
        state, moves = queue.popleft()
        # Check if we reached the target combination
        if state == target:
            return moves
        
        for neighbor in get_neighbors(state):
            if neighbor not in visited and neighbor not in dead_set:
                visited.add(neighbor)
                queue.append((neighbor, moves + 1))
    
    # If target is not reached, return -1
    return -1

# Example test case
print(openLock(["0201","0101","0102","1212","2002"], "0202"))
← Back to All Questions