Abstract / Summary

Turn a lock from a start combination to a target by changing one wheel at a time using only valid moves.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 60% (500k+ submissions).

Typical patterns to solve this problem:

• Array
• Breadth First Search
• Hash Table
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic “open the lock” problem using a breadth-first search (BFS) strategy. Starting from the initial combination "0000", it explores all reachable lock states level by level until it either reaches the target combination or exhausts all possibilities. The algorithm avoids deadends and previously visited states by maintaining dedicated sets for quick membership checks.

Key Steps

The first step converts the list of deadends into a hash set, enabling constant-time lookups when checking whether a state is forbidden.

hashed = set(deadends)  # faster lookups

An early exit handles the situation where the target itself or the starting state is a deadend, returning -1 immediately.

if target in hashed or "0000" in hashed:
    return -1

The BFS frontier is represented by the todo set, initially containing only the starting combination. A separate seen set records states that have already been processed, preventing redundant work.

todo = set(["0000"])
seen = set()
steps = 0

The main loop continues while there are states to explore. For each state in the current frontier, the algorithm checks for a match with the target. If found, the current depth (steps) is returned as the minimum number of moves.

while todo:
    next = set()
    for t in todo:
        if t == target:
            return steps
        seen.add(t)
        ...

Inside the inner loop, the code generates the two possible moves for each of the four wheels: rotating up and rotating down. Two helper strings, up and down, map each digit to its successor and predecessor, respectively, handling the wrap-around from 9 to 0 and from 0 to 9.

up   = "1234567890"
down = "9012345678"
for wheel in range(4):
    num = int(t[wheel])
    u = t[:wheel] + up[num] + t[wheel+1:]
    d = t[:wheel] + down[num] + t[wheel+1:]
    if u not in seen and u not in hashed:
        next.add(u)
    if d not in seen and d not in hashed:
        next.add(d)

After processing all states at the current depth, the frontier is updated to the newly generated states, and the step counter is incremented.

todo = next
steps += 1

If the loop terminates without finding the target, the function returns -1, indicating that the lock cannot be opened under the given constraints.

return -1

Edge Cases Handled

The algorithm explicitly checks for two critical edge conditions before commencing the search. First, if the target combination appears in the deadends list, it is unreachable, and the function returns -1. Second, if the initial combination "0000" is itself a deadend, the search cannot start, leading to the same result. These checks prevent unnecessary computation and correctly handle scenarios where the solution is impossible from the outset.

During state expansion, each newly generated combination is verified against both the seen set and the hashed deadends set. This dual check ensures that the algorithm does not revisit states it has already processed and never steps onto a forbidden combination, thereby respecting the constraints of the problem.

The wrap-around behavior of the lock wheels is captured by the up and down strings. For example, rotating up from 9 yields 0, and rotating down from 0 yields 9. This design correctly models the circular nature of each wheel, covering all possible transitions without special-case logic.

Performance Optimizations

The conversion of the deadends list into a hash set (hashed) provides O(1) average-time membership tests, which is essential given the frequent checks performed during state generation.

Using sets for both the current frontier (todo) and the next frontier (next) eliminates duplicate entries automatically. This property reduces the number of states that need to be examined in subsequent iterations, trimming unnecessary work.

The algorithm stores visited states in the seen set only after a state has been dequeued from the frontier. This approach ensures that a state is not prematurely marked as visited, allowing the same state to be discovered via a shorter path within the same BFS level, though the set semantics still prevent duplication across levels.

String slicing (t[:wheel] and t[wheel+1:]) combined with direct indexing into the up and down strings creates new lock combinations efficiently without converting the entire string to a mutable structure. This technique leverages Python’s immutable string handling while keeping the overhead low.

By incrementing the steps counter only after completing a full level of expansion, the algorithm naturally tracks the minimum number of moves required to reach the target, aligning with the BFS property of exploring states in order of increasing distance from the start.

Imagine you have a lock with four little wheels that have numbers from zero to nine. You want to turn those wheels to show a hidden secret code, but some combinations act like traps that you must avoid.

The code starts by looking at the combination zero zero zero zero. It acts like a detective exploring all the possible ways to turn the wheels one step at a time. Every time the detective tries a new combination, it checks if that combination is a trap. If it is a trap, the detective skips it. If it is not a trap, the detective remembers it so that it does not walk in circles.

The detective keeps track of how many moves it takes to get to each new number. It works in layers, moving from the starting point to every neighbor, then to the neighbors of those neighbors, moving like ripples in a pond. It keeps going until all the possibilities are checked or until the secret code is finally found. If the detective reaches the target code, it knows exactly how many turns it took to get there. If it runs out of moves and never reaches the secret code, then the lock remains closed.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python					TS
	WalkCCC	C++	Java
	leetcode.ca	C++	Java	Python			Go		TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	gouthampradhan		Java
	halfrost						Go
	JoshCrozier				JS
	Krazune	C++
	lkwq007			Python
	ruoru					Rust
	suxrobGM							C#
	trung-hn			Python
	varunu28		Java
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
Krazune	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality