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.

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

python

▶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

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.

06

Complexity

Time

O(10^4)

Space

O(10^4)

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