LeetCode #752 Medium

Open the Lock

A 4-wheel lock starts at 0000; find the minimum number of turns to reach target, avoiding any state in deadends.

bfsimplicit-graph

02

Intuition

The trap that catches people fastest is forgetting to check whether the start 0000 is itself a deadend - if it is, the lock cannot be turned even once, and the answer is -1 before any BFS runs at all, no matter how close 0000 looks to target. Beyond that, this is BFS over an implicit state graph again: each 4-digit state has 8 neighbors, one wheel turned up or down, and the wheels wrap, so turning a wheel down from 0 lands on 9, not -1. Generate the 8 neighbors on the fly, skip deadends and visited states, and BFS layer count is the minimum number of turns.

How to spot this pattern

BFS over lock states, with deadends folded into the visited set at initialisation. That single trick means the expansion loop needs no separate deadend test — an unreachable state and an already-seen state are handled identically.

03

Approach

1

Guard the start

If '0000' is itself in deadends, the lock is stuck before a single turn, so return -1 immediately.

2

Generate 8 neighbors with wrap-around

For each of the 4 wheels, turning up adds 1 mod 10 and turning down subtracts 1 mod 10 (so 0 wraps to 9). A candidate state is valid if it is not a deadend and not already visited.

3

BFS layer = turn count

Track turns from '0000' (0 turns). The moment target is popped from the queue, its turn count is the minimum, since BFS explores shortest paths first.

04

Solution & live demo

▶1class Solution:
▶2    def openLock(self, deadends, target):
▶3        from collections import deque
▶4        dead = set(deadends)
▶5        if '0000' in dead:
▶6            return -1
▶7        visited = {'0000'} | dead
▶8        q = deque([('0000', 0)])
▶9        while q:
▶10            state, d = q.popleft()
▶11            if state == target:
▶12                return d
▶13            for i in range(4):
▶14                digit = int(state[i])
▶15                for delta in (1, -1):
▶16                    nd = (digit + delta) % 10
▶17                    cand = state[:i] + str(nd) + state[i+1:]
▶18                    if cand not in visited:
▶19                        visited.add(cand)
▶20                        q.append((cand, d+1))
▶21        return -1

05

Common pitfalls

Not wrapping the digits

✗ Wrong

nd = digit + delta

✓ Right

nd = (digit + delta) % 10

The wheels are circular: 9 turns to 0 and 0 turns to 9. Without the modulo the digit goes out of range and the state string becomes invalid or throws.

Checking deadends separately in the loop

✗ Wrong

if cand not in visited and cand not in dead:

✓ Right

visited = {'0000'} | dead

Two conditions to keep in sync at every expansion. Seeding the visited set with the deadends makes them unreachable by construction, with one lookup instead of two.

Missing the case where the start is a deadend

✗ Wrong

q = deque([('0000', 0)])

✓ Right

if '0000' in dead:
    return -1

If the initial state is blocked the lock can never be turned, but the BFS would still expand from it since it was enqueued before any check. The guard has to come before the seed.

06

Edge cases

'0000' is itself a deadend

Return -1 before any traversal.

target is '0000'

Zero turns needed, found immediately.

Deadends block every path

BFS queue empties without reaching target; return -1.

Wheel wraps 0 to 9

Turning down from 0 must land on 9, not -1 or an invalid digit.

07

Complexity

Time

O(10^4)

Space

O(10^4)

At most 10000 4-digit states, each generating 8 neighbors.