• 1 <= deadends.length <= 500
• deadends[i].length == 4, target.length == 4
• All strings consist of digits only
• target will not appear in deadends
• target is not "0000"
• "0000" itself may be a deadend, in which case the lock cannot even be started.

The statement is about a physical object, so start by translating it into something countable. A state is one complete display of four digits — not one wheel, but the whole code, since it is the whole code that gets compared against the deadend list. How many states exist? Four wheels with ten positions each gives 10 × 10 × 10 × 10 = 10,000.

That number decides the shape of the solution before any algorithm is chosen. Ten thousand states, each with 8 possible moves, is 80,000 transitions in total — trivial for a computer. So there is no need for a formula or a shortcut. Visiting every reachable state, once, is entirely affordable. The only requirement is to visit each one once.

Making that count is a habit worth building. In any puzzle about configurations, work out how many configurations exist. If the number is small, an exhaustive search is the answer and the interview is really about doing it without redundancy. If it explodes, you need pruning or a completely different idea.

Recast the problem in the vocabulary of paths:

Now "minimum number of moves" is literally "shortest path from 0000 to target", and every move costing the same is the property that makes the easy method valid.

Why does equal cost matter so much? Because it means you can expand outward in layers and trust the order of discovery. Layer 1 is all codes one move from the start, layer 2 is all unclaimed codes one move from those, and so on. A code first appears in the layer equal to its true distance — earlier is impossible, since that would require a shorter route which by definition does not exist, and later cannot happen, because the moment a layer-d code is expanded it claims all of its unclaimed neighbours for layer d+1. The first arrival at target is therefore the best arrival, and the search can stop right there.

This layered expansion is Breadth-First Search. It needs a queue, which returns codes in the order they were found; that FIFO order is what stops layers from mixing. Swap in a stack and the search dives down one long chain of turns before finishing the current layer, and the first time it stumbles onto target the move count is just some route, not the shortest.

Two details are specific to this problem: generating the 8 neighbours with wrap-around, and handling deadends.

Wrap-around is arithmetic. Adding 1 to a digit and taking the remainder on division by 10 turns 9 into 0. Subtracting 1 the same way turns 0 into 9, because in Python (0 - 1) % 10 is 9. Writing both directions as (d + delta) % 10 with delta of +1 and -1 removes every special case.

from collections import deque

def open_lock(deadends, target):
    dead = set(deadends)                  # set: constant-time membership
    if "0000" in dead:
        return -1
    if target == "0000":
        return 0

    queue = deque([("0000", 0)])
    visited = {"0000"}

    while queue:
        code, turns = queue.popleft()
        if code == target:
            return turns

        for i in range(4):                        # which wheel
            for delta in (1, -1):                 # which direction
                digit = (int(code[i]) + delta) % 10
                nxt = code[:i] + str(digit) + code[i + 1:]
                if nxt not in dead and nxt not in visited:
                    visited.add(nxt)              # claim on discovery
                    queue.append((nxt, turns + 1))
    return -1

Note also that deadends and visited codes are rejected at the same point, by the same kind of check. That is the graph view paying off: a jammed code and an already-explored code are both simply not somewhere to go, so they need no separate logic.

Each of at most 10,000 codes is expanded once, and each expansion builds 8 strings of 4 characters. The work is O(10⁴ × 8) with O(10⁴) memory — a fixed budget that does not grow with the input, since the deadend list only ever shrinks the space.

Take deadends {8887, 8889, 8878, 8898, 8788, 8988, 7888, 9888} with target 8888.

The search starts at 0000 and spreads normally. Nothing near the origin is blocked, so layer 1 holds the eight codes 1000, 9000, 0100, 0900, 0010, 0090, 0001, 0009, layer 2 holds everything two turns out, and the wave keeps growing. Every code that differs from 8888 in at least one wheel by two or more slots gets claimed eventually.

But look at what happens at the boundary. To reach 8888 the last move must come from a code differing in exactly one wheel by one slot — and those are exactly 8887, 8889, 8878, 8898, 8788, 8988, 7888 and 9888. All eight are deadends, so all eight fail the nxt not in dead test and are never queued. The search therefore never generates 8888 at all. Eventually every reachable code is claimed, the queue drains, the loop exits, and the answer is -1.

Two things are worth noticing. The target was never touched even though it is not itself a deadend — reachability is about the approaches, not the destination. And the -1 falls out of the queue emptying naturally; no separate detection is needed.

Now the first example, with deadends {0201, 0101, 0102, 1212, 2002} and target 0202. The tempting short route is 0000, 0100, 0200, 0201, 0202 — four moves. But 0201 is jammed, so when 0200 generates it the code is rejected and the route dies there. Meanwhile 0100 is also a deadend, so even that first step is unavailable. BFS does not need to reason about any of this; it simply never queues those codes, and its expanding layers find the six-move route 0000, 1000, 1100, 1200, 1201, 1202, 0202 as soon as layer 6 is reached. The answer is 6.

Strip away the wheels and this is the same shape as the word-transformation problem: a set of configurations, a rule generating the legal moves from any configuration, some configurations forbidden, and a question about the minimum number of moves. The differences are cosmetic — codes instead of words, wheel turns instead of letter swaps.

What distinguishes this one is that the state space is finite and countable in advance. You know before writing a line that there are 10,000 states. In the word problem, the space is bounded by the dictionary; in a puzzle like the sliding 8-puzzle it is 9 factorial, or 362,880; in a problem about arbitrary integers it may be unbounded, and then you need a cutoff or you never terminate. Sizing the space first tells you whether an exhaustive search is even an option.

The same doubling trick applies here as elsewhere. Searching outward from 0000 alone expands roughly 8^d codes by depth d. Searching simultaneously backward from target and expanding whichever frontier is smaller has both sides meet around depth d/2, cutting the number of codes examined dramatically. It is valid because turning a wheel up is undone by turning it down — the move relation is symmetric, so the graph can be walked in either direction.

Train the reflex: when a puzzle asks for the fewest moves between two configurations, count the configurations first. A small, countable space plus uniform move costs means BFS, and the only real work left is generating neighbours correctly and claiming each state exactly once.