Lockboxes
Lesson 2 of 11
2Lockboxes
A puzzle that looks like keys and boxes but is really your first graph search: starting from box zero, what can you reach?
What the picture shows: Start at box 0 and open every box whose key we find, until no new key appears. Any box left closed makes the answer False.
Map of this part
The concepts in order, click any one to jump to it:
Two ways into the same idea
There are locked boxes, and each box holds keys to other boxes. The first box is open. Can you open them all? Open the first and take its keys, use them to open what you can and collect new keys, until no new key is left. Any box still locked means the answer is no.
Boxes are nodes and keys are edges, so the problem is reachability in a directed graph. You solve it with depth-first DFS or breadth-first BFS search plus a set of opened boxes to avoid cycles, in O(V + E) time.
Required fundamentals
The set
set checks membership in roughly constant time O(1), while a list walks the whole thing. That single difference is what turns a slow solution into a fast one.
The stack
A plain Python list is enough: append pushes to the end and pop pops from the end. That is a stack with no library at all.
while with a changing condition
We do not know in advance how many turns we need, so the loop runs "as long as there is work left". This is the case where while beats for.
The idea of a graph
You need no prior graph course, this project is your introduction to one. Just know that a "node" is a point and an "edge" is an arrow between two points.
Core concepts
The problem: you have n boxes numbered 0 to n-1. Box 0 is unlocked, and each box may hold keys to other boxes. The question: can you open all of them?
1Restating the problem: this is a graph
Swap the words and the puzzle disappears: each box is a node, and each key is an arrow from the box holding it to the box it opens. The question becomes: is every node reachable from node zero?
That is called a reachability problem, and its solution is standard: start at the entry point, follow every arrow you can, record every node you reach, then compare how many you reached with the total.
2Why do we need the opened set?
Two reasons, either one sufficient:
- Preventing an infinite loop. If box 0 holds key 2 and box 2 holds key 0, then without recording what has been opened you would bounce between them forever.
- Counting. At the end we need to know how many boxes we opened. The set prevents double counting when we reach the same box by two different paths.
3Keys with no boxes
The brief says it outright: "there can be keys that do not have boxes". So you may be handed key 42 while only 5 boxes exist. That is why the 0 <= key < n guard is not decoration, without it you get IndexError on boxes[42].
4Depth-first or breadth-first?
| DFS (depth-first) | BFS (breadth-first) | |
|---|---|---|
| Structure | stack, pop() from the end | deque, popleft() from the front |
| Path | Dives down one branch to its end, then backtracks | Opens all nearby boxes first |
| Result here | Exactly the same | Exactly the same |
| Complexity | O(n + k) | O(n + k) |
Since the question is "do we reach all of them?" and the shortest path does not matter, both are correct. The stack is simpler because it is a plain list with no import. (k is the total number of keys, the sum of the inner list lengths.)
5The naive solution and why we avoid it
The first idea that comes to mind: walk every box, take the keys from the open ones, and repeat until nothing changes. That does give the right answer, but in the worst case you need n passes and each pass is O(n), so it becomes O(n²). The stack search visits every box exactly once.
opened instead of a set. key in opened_list inside a loop quietly makes the solution O(n²), because every membership check walks the whole list. Choosing the structure is not cosmetic, it is the complexity.How it works
Three pictures: the search path itself, then the failing test case as a graph, then the naive solution so you can see the difference with your own eyes.
Diagram 3, The search path: pop a box off the stack, take every new valid key from it, push its box, until the stack empties.
Diagram 4, The third test case as a graph: boxes 5 and 6 (dashed) never receive an arrow, and their own keys do not help them, because a key inside a locked box may as well not exist.
Diagram 5, The naive solution: a full sweep over every box on each pass, possibly opening just one box per sweep, doubling the work for nothing.
Worked example, step by step
We write the solution, run it, then walk the failing case step by step. Every output below is real.
Step 1, the solution
#!/usr/bin/python3
"""0-lockboxes"""
def canUnlockAll(boxes):
"""Return True if every box can be opened starting from box 0."""
n = len(boxes)
if n == 0:
return True
opened = {0}
stack = [0]
while stack:
box = stack.pop()
for key in boxes[box]:
if 0 <= key < n and key not in opened:
opened.add(key)
stack.append(key)
return len(opened) == nStep 2, running it
$ cat main_0.py
#!/usr/bin/python3
canUnlockAll = __import__('0-lockboxes').canUnlockAll
boxes = [[1], [2], [3], [4], []]
print(canUnlockAll(boxes))
boxes = [[1, 4, 6], [2], [0, 4, 1], [5, 6, 2], [3], [4, 1], [6]]
print(canUnlockAll(boxes))
boxes = [[1, 4], [2], [0, 4, 1], [3], [], [4, 1], [5, 6]]
print(canUnlockAll(boxes))
$ ./main_0.py
True
True
FalseStep 3, the edges
>>> canUnlockAll([[]]) # one box, already open True >>> canUnlockAll([[1], []]) # box 0 holds the key to box 1 True >>> canUnlockAll([[], [1]]) # box 1 unreachable; its own key is useless False >>> canUnlockAll([[1, 9, 42], []]) # keys with no box: harmlessly ignored True
That last line matters: keys 9 and 42 have no boxes, and the solution ignores them quietly thanks to the range guard.
Step 4, walk the failing case
Tracing the third case, one pop at a time
The case: [[1,4],[2],[0,4,1],[3],[],[4,1],[5,6]], seven boxes.
Start: opened = {0} and stack = [0].
Pop 0. Its keys are [1, 4]. Both are new and valid, so we add them.
opened = {0,1,4} · stack = [1,4]
Pop 4 (the end of the stack, this is what depth-first means). Its keys are [], so there is nothing to add.
opened = {0,1,4} · stack = [1]
Pop 1. Its key is [2], which is new, so we add it.
opened = {0,1,2,4} · stack = [2]
Pop 2. Its keys are [0, 4, 1]: box 3 is new so we add it, while 0 and 4 are already open so we skip them, this is exactly where the set prevents a cycle.
opened = {0,1,2,3,4} · stack = [3]
Pop 3. Its keys are []. The stack is empty.
The arithmetic: len(opened) = 5 and n = 7, and 5 != 7 → False.
Boxes 5 and 6 were never reached. Note that box 6 holds keys 5 and 6, but those keys are themselves inside a locked box, so they are worthless.
stack = [0] for deque([0]) and pop() for popleft() and you have a breadth-first search. The result is the same, but the visit order differs, and that order is what matters in "shortest path" problems later.Myth vs. reality
| The myth | The reality |
|---|---|
| “The problem is about keys, so I should process keys one by one.” | The keys are not the goal, the opened boxes are. Think about what you have reached, not what you are holding. |
| “If a key exists, the box is open.” | A key that sits inside a locked box may as well not exist. Reachability only travels through open boxes. |
| “I must verify every key gets used.” | No. Extra, duplicate, and box-less keys are all fine. The only question is whether every box got opened. |
“If box 0 is empty the answer is False.” | Only when there is more than one box. [[]] returns True, a single box that is already open. |
“DFS and BFS give different results.” | For reachability: exactly the same result. Only the visit order differs, and that matters in other problems. |
“I can just use boxes and count at the end.” | The input never tells you which boxes got opened. You need a separate record, otherwise you cannot tell "reached" from "exists". |
Where it is used in practice
Dependency resolution
"Can every package I need be installed starting from this one?" is literally the same problem: a package is a node, a dependency is an arrow.
Permissions and roles
A role grants other roles, which grant others still. "What can this user actually reach?" is graph reachability.
Garbage collection
The runtime starts from the roots and follows references. Any object the search never reaches is garbage. Your algorithm here is the "mark" half of mark-and-sweep.
Web crawling
Start at a page, follow the links, never visit a page twice. The opened set is exactly "pages already visited".
Try it yourself
You remove only the key not in opened guard and leave everything else. What is the worst that happens?
Without that guard we keep pushing already-opened boxes back onto the stack. If box 0 holds key 2 and box 2 holds key 0, the stack never empties, which is the first reason opened exists, before counting is even considered.
Quick review flashcards
opened?O(1) instead of O(n), which makes the solution O(n+k) instead of O(n²).key not in opened guard before pushing. Without it, cycles spin forever.0 <= key < n guard?boxes[key] for a large key raises IndexError.len(opened) == n, and nothing else.O(n + k) where n is the number of boxes and k the total number of keys, each box visited once, each key read once.Check your understanding
1. Why does [[1], []] return True while [[], [1]] returns False?
In the first, box 0 (the open one) holds key 1, so we reach both. In the second, box 0 is empty so we never move; the key to box 1 sits inside box 1, which is locked. A key only helps you if it is in a box you have reached.
2. Does the order of keys inside a box change the result?
Not the result, yes the visit order. The set of reachable boxes does not depend on arrow order, but your hand trace will differ, which confuses a lot of people while debugging.
3. (Spot the bug) Your solution returns True on a valid 100-box case, works, but is painfully slow. What do you check first?
The type of opened. If it is a list, every in walks the whole list, so the solution is correct but O(n²). Make it a set and you are done.
4. Someone uses stack.pop(0) instead of stack.pop(). Is the solution still correct?
Correct, yes (it has become roughly BFS), but pop(0) on a Python list is O(n) because it shifts every element. For breadth-first use collections.deque with popleft().
5. (Decision) The input has a million boxes and deep nesting. Recursive DFS or an explicit stack?
An explicit stack. Recursion hits Python's depth limit (about 1000 by default) and raises RecursionError. An explicit stack is bounded only by memory, and this is a general rule: every recursive DFS can be written with a stack.
Resources for this part
Sorted by kind: start with the official docs when you want the precise reference, or with an article or video when you want the explanation first.
Resources for this lesson
Grouped by type. Start with the official docs for precision, or an article or video for the explanation.
Done with this lesson?
Sign in to save your progress.