Maximum Candies You Can Get from Boxes: BFS Simulation

You have n boxes, each labeled 0 to n - 1. Each box has a status (open or locked), a number of candies inside, a set of keys to other boxes, and a list of other boxes contained inside it. You are given some initial boxes. You can open a box if you have it and it is either already open or you hold its key. When you open a box, you collect its candies, take its keys, and receive its contained boxes. Return the maximum number of candies you can collect.

This is LeetCode 1298: Maximum Candies You Can Get from Boxes, and it is an excellent exercise in BFS simulation with multiple interacting state variables.

Why this problem matters

At first glance this looks like a graph traversal problem, and it is. But it adds a twist that makes it trickier than standard BFS: you need two conditions to process a box. You must both have the box (it was an initial box or contained inside another opened box) and be able to open it (its status is open, or you hold its key). Keys might arrive before boxes, boxes might arrive before keys, and the order in which things unlock depends entirely on the simulation.

This "dual-condition gating" pattern shows up in problems where resources unlock other resources. Think of it as a dependency resolution problem: you cannot proceed until two independent prerequisites are both satisfied, and satisfying one might cascade into satisfying others.

The key insight

Use BFS with a queue of boxes you can currently open. Maintain two sets alongside the queue: boxes you possess (but might not be able to open yet) and keys you hold (but might not have the matching box for yet). When you open a box, three things happen: you collect its candies, you gain its keys, and you receive its contained boxes. Each new key might unlock a box you already have. Each new box might already be unlockable with a key you already hold. In either case, add the newly openable box to the queue.

The algorithm:

1. Start with the initial boxes. For each one that is already open, add it to the queue. Track all of them in a "have box" set.
2. Process the queue. For each box you dequeue, collect its candies, add its keys to your key set, and add its contained boxes to your "have box" set.
3. For each new key, check if you already have that box but could not open it before. If so, add it to the queue.
4. For each newly received box, check if it is already open or you already hold its key. If so, add it to the queue.
5. Continue until the queue is empty.

The solution

from collections import deque

def max_candies(
    status: list[int],
    candies: list[int],
    keys: list[list[int]],
    contained_boxes: list[list[int]],
    initial_boxes: list[int],
) -> int:
    n = len(status)
    have_box = [False] * n
    have_key = [False] * n
    visited = [False] * n
    queue = deque()

    for box in initial_boxes:
        have_box[box] = True
        if status[box] == 1:
            queue.append(box)
            visited[box] = True

    total = 0

    while queue:
        box = queue.popleft()
        total += candies[box]

        for k in keys[box]:
            have_key[k] = True
            if have_box[k] and not visited[k]:
                visited[k] = True
                queue.append(k)

        for b in contained_boxes[box]:
            have_box[b] = True
            if (status[b] == 1 or have_key[b]) and not visited[b]:
                visited[b] = True
                queue.append(b)

    return total

Let's walk through what each piece does.

The setup phase marks every initial box as "possessed" and adds the ones that are already open to the BFS queue. The visited array prevents processing the same box twice.

Inside the BFS loop, we dequeue a box and immediately collect its candies. Then we process its keys: for each key, we mark it as held. If we already possess that box but have not visited it yet, the key just unlocked it, so we enqueue it. Next, we process contained boxes: for each one, we mark it as possessed. If it is either already open (status 1) or we hold its key, and we have not visited it yet, we enqueue it.

The critical detail is that keys and boxes can arrive in any order. A key might arrive for a box you do not have yet. A box might arrive that you do not have a key for yet. The BFS handles this naturally because each new key checks against possessed boxes, and each new box checks against held keys. Whenever both conditions are satisfied, the box enters the queue.

Visual walkthrough

Notice the interesting moment at Step 5: we get the key for Box 4, but we never received Box 4 from any opened box. Having a key without having the box is not enough. This is a common edge case that makes the dual-condition check essential.

Complexity analysis

Time is O(n + total keys + total contained boxes). We visit each box at most once. We iterate through each box's keys and contained boxes exactly once when that box is opened. The total work across all boxes is the sum of all keys lists and all contained boxes lists, plus n for the boxes themselves.

Space is O(n) for the three boolean arrays (have_box, have_key, visited) and the BFS queue. The queue holds at most n boxes.

The building blocks

1. BFS with state tracking

The core pattern of BFS where processing a node changes global state that affects future decisions:

queue = deque(starting_nodes)
visited = set(starting_nodes)

while queue:
    node = queue.popleft()
    process(node)
    for new_node in discover(node):
        if can_process(new_node) and new_node not in visited:
            visited.add(new_node)
            queue.append(new_node)

This is standard BFS with one important difference: can_process depends on state that evolves as you process nodes. In Rotting Oranges, every discovered cell is immediately processable. Here, a discovered box might not be openable yet. The state-tracking BFS pattern handles this by re-checking conditions whenever state changes (new key acquired, new box received).

2. Dual-condition gating

The pattern where a node becomes processable only when two independent conditions are both true:

if have_box[i] and (status[i] == 1 or have_key[i]):
    queue.append(i)

You check this condition in two places: when you receive a new box (check if you can open it) and when you receive a new key (check if you have the box). This ensures that no matter which condition is satisfied first, the box enters the queue as soon as both are met. This same pattern appears in problems with resource dependencies, where progress requires collecting multiple prerequisites that arrive in unpredictable order.

Edge cases

• All boxes are open from the start: every initial box can be processed immediately, and every contained box is open too. BFS proceeds without any key-checking logic, and you collect everything reachable.
• All boxes are locked with no keys anywhere: you cannot open any box. Return 0.
• Circular key dependencies: Box A has the key for Box B, and Box B has the key for Box A. Neither can be opened unless one of them has status 1 or another box provides a key. If both are locked and no external key exists, both remain locked.
• Key arrives before box: you receive a key for Box 5 from Box 2, but Box 5 is not discovered until Box 7 is opened. The key sits in have_key until Box 5 enters have_box, at which point the condition check triggers and Box 5 is enqueued.
• Box arrives already open: a contained box with status[i] == 1 does not need a key. It goes straight into the queue when discovered.
• Empty initial boxes: no boxes to start with. Return 0.

From understanding to recall

You have seen how the BFS simulation juggles three pieces of state: boxes you have, keys you hold, and boxes you have visited. The logic is clean, but the interplay between keys and boxes creates subtle ordering issues. Under interview pressure, it is easy to forget one of the two check points (when gaining a key vs. when gaining a box) or to skip the visited guard.

Spaced repetition makes this automatic. You practice writing the dual-condition BFS loop, the key-arrival check, and the box-arrival check from memory at increasing intervals. After a few rounds, the two-condition pattern becomes second nature. You see "two prerequisites must both be satisfied" in a problem, and the template flows out without hesitation.

Related posts

• Open the Lock - BFS with state exploration, finding shortest path through state space
• Number of Islands - Classic BFS/DFS graph traversal on a grid
• Clone Graph - BFS traversal with tracking visited nodes

CodeBricks breaks Maximum Candies You Can Get from Boxes into its BFS-with-state-tracking and dual-condition-gating building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a simulation-style BFS problem shows up in your interview, you do not think about it. You just write it.