Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Owning a box and being able to unlock it are different conditions. A locked box discovered now may become usable after another box provides its key. We therefore remember both possessed boxes and acquired keys, and revisit a possessed box when a new key makes it usable.

Approach

Queue the initial boxes and record possession. Skip a queued box if it is already opened or remains locked without a key. Otherwise collect its candies once, record its keys, and queue corresponding possessed boxes for reconsideration. Python excludes already-opened key targets before enqueueing; JavaScript skips them when dequeued. Record contained boxes as possessed: Python queues each contained entry, while JavaScript queues only newly discovered boxes. Continue until the queue empties. Opening an available box cannot remove opportunities, so the process collects every reachable, unlockable box. Duplicate queue entries are harmless because the opened set prevents repeated candy counts.

class Solution:
    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
        res = 0
        opened = set()
        have_keys = set()
        seen = set(initialBoxes)
        q = deque(initialBoxes)

        while q:
            box = q.popleft()
            if (status[box] == 0 and box not in have_keys) or box in opened:
                continue

            opened.add(box)
            res += candies[box]

            for x in keys[box]:
                have_keys.add(x)
                if x in seen and x not in opened:
                    q.append(x)

            for cb in containedBoxes[box]:
                if cb not in seen:
                    seen.add(cb)
                q.append(cb)

        return res

Complexity analysis

Let B be the number of boxes, K the total key entries, and C the total contained-box entries. Each box is opened at most once and its key and contained-box lists are scanned once, giving O(B + K + C) time. The sets use O(B) space, while repeated discoveries can leave O(K) queue entries pending or retained, so auxiliary space is O(B + K).