Problem statement

There are n boxes labelled 0 to n - 1. For each box i:

• status[i] is 1 if the box is open and 0 if it is closed;
• candies[i] is the number of candies inside;
• keys[i] lists the boxes whose keys are inside box i;
• containedBoxes[i] lists the boxes found inside box i.

You start holding the boxes in initialBoxes. You can take the candies from any box you hold that is open, and use the keys and boxes inside it. A key opens its box whenever you come to hold that box (or immediately, if you already hold it).

Return the maximum number of candies you can collect.

Example 1

Input: status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]
Output: 16
Explanation: Box 0 gives 7 candies and boxes 1 and 2. Box 2 is open: 4 candies and the key to box 1. Box 1 gives 5 candies and box 3, which stays locked. 7 + 4 + 5 = 16.

Example 2

Input: status = [1,0,0,0,0,0], candies = [1,1,1,1,1,1], keys = [[1,2,3,4,5],[],[],[],[],[]], containedBoxes = [[1,2,3,4,5],[],[],[],[],[]], initialBoxes = [0]
Output: 6

Example 3

Input: status = [0], candies = [5], keys = [[]], containedBoxes = [[]], initialBoxes = [0]
Output: 0
Explanation: The only box is locked and its key is nowhere.

Constraints

• n == status.length == candies.length == keys.length == containedBoxes.length
• 1 <= n <= 1000
• status[i] is 0 or 1
• 1 <= candies[i] <= 1000
• 0 <= keys[i].length <= n
• 0 <= keys[i][j] < n, and the values of keys[i] are unique
• 0 <= containedBoxes[i].length <= n
• 0 <= containedBoxes[i][j] < n, and the values of containedBoxes[i] are unique
• each box is contained in at most one box
• 0 <= initialBoxes.length <= n
• 0 <= initialBoxes[i] < n

Hints for Maximum Candies You Can Get from Boxes

1. Hint 1

   A box can be opened exactly when you hold it and it is open or you have its key. Both facts only ever become true, never false.

2. Hint 2

   Keep a queue of boxes ready to open. Whenever a box is opened, it may make other boxes ready: through a key it contains, or through a box it contains.

3. Hint 3

   Mark a box as queued the moment it becomes ready so it is opened once. Sum the candies of every box you open.

How to solve Maximum Candies You Can Get from Boxes

Opening a box only ever adds keys and boxes, so there is no choice to make — open everything that can ever be opened. A breadth-first search over "ready" boxes does this in linear time.

Approach

1. Track held[i], canOpen[i] (initially status[i]) and queued[i].
2. Mark every initial box as held; queue those that can be opened.
3. Pop a box, add its candies. For every key k inside: set canOpen[k], and queue k if it is held and not yet queued. For every box c inside: set held[c], and queue it if it can be opened and is not yet queued.
4. Return the total when the queue empties.

Why it works

Holding a box and being able to open it are monotone facts, so opening a box early never prevents anything later. The queue opens a box as soon as both facts hold, and each event that could complete them (finding a key, finding a box) re-checks the affected box. Therefore every box that any strategy could open is opened, exactly once.

Complexity

• Time — O(n + total keys + total contained boxes)
• Space — O(n)

Pitfalls

• A key found for a box you do not hold yet must be remembered — the box may turn up later.
• A box can become ready through a key or through being found; check readiness in both places.
• Use a queued flag so a box is never counted twice.

Reference solution

Python

from collections import deque
from typing import List

def maxCandies(status: List[int], candies: List[int], keys: List[List[int]],
               containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
    n = len(status)
    can_open = status[:]
    held = [False] * n
    queued = [False] * n
    q = deque()
    for b in initialBoxes:
        held[b] = True
        if can_open[b] and not queued[b]:
            queued[b] = True
            q.append(b)
    total = 0
    while q:
        b = q.popleft()
        total += candies[b]
        for k in keys[b]:
            can_open[k] = 1
            if held[k] and not queued[k]:
                queued[k] = True
                q.append(k)
        for c in containedBoxes[b]:
            held[c] = True
            if can_open[c] and not queued[c]:
                queued[c] = True
                q.append(c)
    return total

Java

public static int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
    int n = status.length, total = 0, head = 0, tail = 0;
    int[] canOpen = status.clone(), q = new int[n];
    boolean[] held = new boolean[n], queued = new boolean[n];
    for (int b : initialBoxes) {
        held[b] = true;
        if (canOpen[b] == 1 && !queued[b]) { queued[b] = true; q[tail++] = b; }
    }
    while (head < tail) {
        int b = q[head++];
        total += candies[b];
        for (int k : keys[b]) {
            canOpen[k] = 1;
            if (held[k] && !queued[k]) { queued[k] = true; q[tail++] = k; }
        }
        for (int c : containedBoxes[b]) {
            held[c] = true;
            if (canOpen[c] == 1 && !queued[c]) { queued[c] = true; q[tail++] = c; }
        }
    }
    return total;
}

C++

int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
    int n = status.size(), total = 0;
    vector<int> canOpen = status;
    vector<bool> held(n, false), queued(n, false);
    queue<int> q;
    for (int b : initialBoxes) {
        held[b] = true;
        if (canOpen[b] && !queued[b]) { queued[b] = true; q.push(b); }
    }
    while (!q.empty()) {
        int b = q.front(); q.pop();
        total += candies[b];
        for (int k : keys[b]) {
            canOpen[k] = 1;
            if (held[k] && !queued[k]) { queued[k] = true; q.push(k); }
        }
        for (int c : containedBoxes[b]) {
            held[c] = true;
            if (canOpen[c] && !queued[c]) { queued[c] = true; q.push(c); }
        }
    }
    return total;
}

JavaScript

var maxCandies = function(status, candies, keys, containedBoxes, initialBoxes) {
    var n = status.length, canOpen = status.slice(), held = [], queued = [], q = [], total = 0;
    for (var i = 0; i < n; i++) { held.push(false); queued.push(false); }
    for (var a = 0; a < initialBoxes.length; a++) {
        var b0 = initialBoxes[a];
        held[b0] = true;
        if (canOpen[b0] && !queued[b0]) { queued[b0] = true; q.push(b0); }
    }
    for (var h = 0; h < q.length; h++) {
        var b = q[h];
        total += candies[b];
        for (var x = 0; x < keys[b].length; x++) {
            var k = keys[b][x];
            canOpen[k] = 1;
            if (held[k] && !queued[k]) { queued[k] = true; q.push(k); }
        }
        for (var y = 0; y < containedBoxes[b].length; y++) {
            var c = containedBoxes[b][y];
            held[c] = true;
            if (canOpen[c] && !queued[c]) { queued[c] = true; q.push(c); }
        }
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard