algoadvance

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example, '9' can turn to '0', and '0' can turn to '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends deadends, meaning if the lock displays any of these codes, the lock will be stuck in that state permanently, and you cannot turn the wheels anymore.

You are also given a target target, representing the code that you want to unlock.

Return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Clarifying Questions

  1. Q: Are the elements in deadends unique, or can they repeat? A: The elements in deadends are unique.

  2. Q: Can target be in the list of deadends? A: No, target will not be a part of deadends.

  3. Q: What should we return if the initial state '0000' is in deadends? A: If '0000' is in deadends, you should return -1 immediately since the lock is already stuck.

Strategy

We’ll use a Breadth-First Search (BFS) approach to explore all possible states from '0000'. BFS is suitable here because it explores all nodes at the present depth level before moving on to nodes at the next depth level. This ensures that we find the shortest path (minimum number of turns) to the target.

  1. Initialization: Start from '0000'. If it is in deadends, return -1.
  2. Queue: Use a queue to perform BFS. Initialize the queue with the initial state '0000' and a depth of 0.
  3. Visited Set: Keep track of visited states to avoid cycles.
  4. Generate Next States: For each current state, generate all possible states by turning each wheel clockwise and counterclockwise.
  5. Check Deadends: Skip states that are in the deadends list.
  6. Target Check: If we reach the target state, return the current depth (number of moves).
  7. End Condition: If the queue is exhausted without finding the target, return -1.

Code Implementation

from collections import deque

def openLock(deadends, target):
    deadends = set(deadends)
    start = '0000'
    
    # If the initial lock position is a deadend
    if start in deadends:
        return -1
    
    # Use a queue to perform BFS
    queue = deque([(start, 0)])
    visited = set([start])
    
    while queue:
        current_state, turns = queue.popleft()
        
        # If we've reached the target
        if current_state == target:
            return turns
        
        # Generate next states
        for i in range(4):
            for direction in (-1, 1):
                next_state = list(current_state)
                next_state[i] = str((int(next_state[i]) + direction) % 10)
                next_state = ''.join(next_state)
                
                # If the state is not visited and not a deadend
                if next_state not in visited and next_state not in deadends:
                    visited.add(next_state)
                    queue.append((next_state, turns + 1))
                    
    # If we exhaust the queue and do not find the target
    return -1

# Example usage:
deadends = ["0201","0101","0102","1212","2002"]
target = "0202"
print(openLock(deadends, target))  # Output: 6

Time Complexity

Try our interview co-pilot at AlgoAdvance.com