Maximum Candies You Can Get from Boxes
Maximum Candies You Can Get from Boxes is a hard graphs problem solved with the bfs / dfs basics pattern.
The best approach, optimal (bfs over openable boxes), runs in O(n + K) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (repeat full scans until nothing changes) up.
Problem
You have n boxes numbered 0 to n - 1. For box i you are told whether it starts open (status[i] == 1) or locked (status[i] == 0), how many candies it holds (candies[i]), which keys lie inside it (keys[i], each key opens the box with that number) and which other boxes lie inside it (containedBoxes[i]).
At the start you hold the boxes listed in initialBoxes. You may open any box you hold that is either open or whose key you have. Opening a box gives you all its candies, keys and inner boxes, which you can then use in turn.
Return the largest number of candies you can collect.
Examples
Example 1
- Input
status = [1, 0, 0, 1], candies = [5, 8, 2, 4], keys = [[1], [], [], []], containedBoxes = [[2, 1], [], [], []], initialBoxes = [0, 3]- Output
17- Why
- Box 0 is open: take 5 candies, the key to box 1 and boxes 2 and 1. Box 1 can now be unlocked (8), box 3 is open (4). Box 2 stays locked, so the total is 5 + 8 + 4 = 17.
Example 2
- Input
status = [0, 1], candies = [10, 3], keys = [[], []], containedBoxes = [[], []], initialBoxes = [0]- Output
0- Why
- The only box you hold is closed and no key for it exists anywhere you can reach.
Example 3
- Input
status = [1, 0, 0], candies = [1, 2, 3], keys = [[2], [], [1]], containedBoxes = [[1, 2], [], []], initialBoxes = [0]- Output
6- Why
- Box 0 gives boxes 1 and 2 plus the key to box 2. Box 2 then gives the key to box 1, which you already hold, so every box gets opened.
Constraints
n == status.length == candies.length == keys.length == containedBoxes.length,1 <= n <= 1000status[i]is0or1;1 <= candies[i] <= 10000 <= keys[i].length, containedBoxes[i].length <= n, all values in[0, n), and the values inside one list are distinct- Every box appears in at most one box's
containedBoxesand is never ininitialBoxesas well. 0 <= initialBoxes.length <= n, values distinct and in[0, n)
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (repeat full scans until nothing changes) | O(n² + K) | O(n) |
| Optimal (BFS over openable boxes) | O(n + K) | O(n) |
1Brute force (repeat full scans until nothing changes)
O(n² + K)Each sweep that changes anything opens at least one box, so there are at most n + 1 sweeps of n boxes; K is the total length of all key and box lists, each read once.O(n)Three boolean arrays of size n.Keep three flags per box: do I hold it, do I have its key, have I opened it. Sweep over all boxes and open every box that is held, not yet opened and openable. Opening a box can unlock others, so keep sweeping until a full sweep opens nothing.
- Mark every initial box as held; mark boxes with
status[i] == 1as unlocked. - Sweep i = 0..n-1: if box i is held, unlocked and not opened, open it: add its candies, unlock every box in
keys[i], hold every box incontainedBoxes[i]. - Repeat sweeps while the last sweep opened something; return the candy total.
class Solution {
public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
int n = status.length;
boolean[] held = new boolean[n], unlocked = new boolean[n], opened = new boolean[n];
for (int b : initialBoxes) held[b] = true;
for (int i = 0; i < n; i++) unlocked[i] = status[i] == 1;
int total = 0;
boolean changed = true;
while (changed) {
changed = false;
for (int i = 0; i < n; i++) {
if (held[i] && unlocked[i] && !opened[i]) {
opened[i] = true;
changed = true;
total += candies[i];
for (int k : keys[i]) unlocked[k] = true;
for (int b : containedBoxes[i]) held[b] = true;
}
}
}
return total;
}
}class Solution:
def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
n = len(status)
held = [False] * n
unlocked = [s == 1 for s in status]
opened = [False] * n
for b in initialBoxes:
held[b] = True
total = 0
changed = True
while changed:
changed = False
for i in range(n):
if held[i] and unlocked[i] and not opened[i]:
opened[i] = True
changed = True
total += candies[i]
for k in keys[i]:
unlocked[k] = True
for b in containedBoxes[i]:
held[b] = True
return totalclass Solution {
public:
int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
int n = status.size();
vector<bool> held(n, false), unlocked(n, false), opened(n, false);
for (int b : initialBoxes) held[b] = true;
for (int i = 0; i < n; i++) unlocked[i] = status[i] == 1;
int total = 0;
bool changed = true;
while (changed) {
changed = false;
for (int i = 0; i < n; i++) {
if (held[i] && unlocked[i] && !opened[i]) {
opened[i] = true;
changed = true;
total += candies[i];
for (int k : keys[i]) unlocked[k] = true;
for (int b : containedBoxes[i]) held[b] = true;
}
}
}
return total;
}
};function maxCandies(status, candies, keys, containedBoxes, initialBoxes) {
const n = status.length;
const held = new Array(n).fill(false);
const unlocked = status.map(s => s === 1);
const opened = new Array(n).fill(false);
for (const b of initialBoxes) held[b] = true;
let total = 0;
let changed = true;
while (changed) {
changed = false;
for (let i = 0; i < n; i++) {
if (held[i] && unlocked[i] && !opened[i]) {
opened[i] = true;
changed = true;
total += candies[i];
for (const k of keys[i]) unlocked[k] = true;
for (const b of containedBoxes[i]) held[b] = true;
}
}
}
return total;
}2Optimal (BFS over openable boxes)
O(n + K)Each box is queued at most once and each entry of every key or box list is read once (K = total list length).O(n)Flag arrays and the queue, all of size n.Treat opening a box as visiting a node. A box enters the queue the first moment it is both held and unlocked. Opening it can only make the boxes in its two lists newly held or newly unlocked, so only those boxes need to be checked again.
- Mark held and unlocked flags as before. Push every initial box that is already unlocked, marking it queued.
- Pop a box, add its candies.
- For each key k in it: set
unlocked[k]; if k is held and not queued, queue it. - For each box b in it: set
held[b]; if b is unlocked and not queued, queue it. - When the queue is empty, return the total.
class Solution {
public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
int n = status.length;
boolean[] held = new boolean[n], unlocked = new boolean[n], queued = new boolean[n];
for (int i = 0; i < n; i++) unlocked[i] = status[i] == 1;
Deque<Integer> queue = new ArrayDeque<>();
for (int b : initialBoxes) {
held[b] = true;
if (unlocked[b] && !queued[b]) { queued[b] = true; queue.add(b); }
}
int total = 0;
while (!queue.isEmpty()) {
int box = queue.poll();
total += candies[box];
for (int k : keys[box]) {
unlocked[k] = true;
if (held[k] && !queued[k]) { queued[k] = true; queue.add(k); }
}
for (int b : containedBoxes[box]) {
held[b] = true;
if (unlocked[b] && !queued[b]) { queued[b] = true; queue.add(b); }
}
}
return total;
}
}class Solution:
def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
n = len(status)
held = [False] * n
unlocked = [s == 1 for s in status]
queued = [False] * n
queue = deque()
for b in initialBoxes:
held[b] = True
if unlocked[b] and not queued[b]:
queued[b] = True
queue.append(b)
total = 0
while queue:
box = queue.popleft()
total += candies[box]
for k in keys[box]:
unlocked[k] = True
if held[k] and not queued[k]:
queued[k] = True
queue.append(k)
for b in containedBoxes[box]:
held[b] = True
if unlocked[b] and not queued[b]:
queued[b] = True
queue.append(b)
return totalclass Solution {
public:
int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
int n = status.size();
vector<bool> held(n, false), unlocked(n, false), queued(n, false);
for (int i = 0; i < n; i++) unlocked[i] = status[i] == 1;
queue<int> q;
for (int b : initialBoxes) {
held[b] = true;
if (unlocked[b] && !queued[b]) { queued[b] = true; q.push(b); }
}
int total = 0;
while (!q.empty()) {
int box = q.front(); q.pop();
total += candies[box];
for (int k : keys[box]) {
unlocked[k] = true;
if (held[k] && !queued[k]) { queued[k] = true; q.push(k); }
}
for (int b : containedBoxes[box]) {
held[b] = true;
if (unlocked[b] && !queued[b]) { queued[b] = true; q.push(b); }
}
}
return total;
}
};function maxCandies(status, candies, keys, containedBoxes, initialBoxes) {
const n = status.length;
const held = new Array(n).fill(false);
const unlocked = status.map(s => s === 1);
const queued = new Array(n).fill(false);
const queue = [];
for (const b of initialBoxes) {
held[b] = true;
if (unlocked[b] && !queued[b]) { queued[b] = true; queue.push(b); }
}
let total = 0;
for (let head = 0; head < queue.length; head++) {
const box = queue[head];
total += candies[box];
for (const k of keys[box]) {
unlocked[k] = true;
if (held[k] && !queued[k]) { queued[k] = true; queue.push(k); }
}
for (const b of containedBoxes[box]) {
held[b] = true;
if (unlocked[b] && !queued[b]) { queued[b] = true; queue.push(b); }
}
}
return total;
}Edge cases to test
- No initial boxes at all (answer 0)
- A key arrives after the box it opens is already in your hands
- A key arrives before you own the box it opens
- Keys for boxes that are already open (harmless)
- Closed boxes that are never reachable
Hints
Hint 1
A box can be opened exactly when you both hold it and it is open or you hold its key. Both conditions only ever become true, never false.
Hint 2
So every time you gain a box or a key, check whether that one box has just become openable.
Hint 3
Use a queue of boxes ready to open, and a visited flag so no box is emptied twice. Total work is the size of all lists.
FAQ
What is the best time complexity for Maximum Candies You Can Get from Boxes?
Optimal (BFS over openable boxes) runs in O(n + K) time and O(n) extra space. Each box is queued at most once and each entry of every key or box list is read once (K = total list length).
Which pattern does Maximum Candies You Can Get from Boxes use?
It is a graphs problem that uses the bfs / dfs basics pattern. Other problems with the same pattern: BFS - Normal + Level by Level, DFS - Recursive + Iterative, Clone Graph.
Is there a brute force solution for Maximum Candies You Can Get from Boxes?
Yes. Brute force (repeat full scans until nothing changes) takes O(n² + K) time and O(n) space. Keep three flags per box: do I hold it, do I have its key, have I opened it.
Which edge cases should I test for Maximum Candies You Can Get from Boxes?
No initial boxes at all (answer 0); A key arrives after the box it opens is already in your hands; A key arrives before you own the box it opens; Keys for boxes that are already open (harmless); Closed boxes that are never reachable.