Maximum Candies You Can Get from Boxes
Asked at Airbnb
Problem
Maximum Candies You Can Get from Boxes starts you with some boxes; each box is open or locked, holds candies, keys to other boxes, and other boxes. You can open any box you have that is open or for which you hold a key. How many candies can you collect? It is a BFS where a box becomes usable only once two conditions — "I have it" and "I can open it" — are both true.
Asked At
| Company | Difficulty | |
|---|---|---|
| Airbnb | Hard | View all Airbnb questions → |
How to Think About It
Order does not matter: opening a box never makes anything worse. So simply keep opening whatever you can until nothing changes.
Track two facts per box: have[b] (you possess it) and canOpen[b] (it starts open or you found its key). A box is processable when both are true and you have not opened it yet.
Use a queue of processable boxes. When you open a box: collect its candies; for each key inside, mark canOpen and enqueue that box if you already have it; for each box inside, mark have and enqueue it if it can be opened.
The "enqueue only when both become true" rule guarantees each box is opened at most once — use an opened flag to be safe.
Walkthrough: status = [1,0,1,0], candies = [7,5,4,100], box 0 contains boxes 1 and 2, box 2 holds the key to box 1, box 1 contains box 3. Open 0 (+7) -> get 1 (locked) and 2 (open). Open 2 (+4) -> key to 1, which we already have, so open 1 (+5) -> get box 3, but it is locked and no key exists. Total 16.
Optimal Approach
Step 1: have[b] = true for each initial box; canOpen[b] = (status[b] == 1).
Step 2: Enqueue every initial box with canOpen; mark it opened.
Step 3: While the queue is not empty, pop box b:
total += candies[b]
For each key k in keys[b]: canOpen[k] = true; if have[k] and not opened[k], open and enqueue it.
For each box c in containedBoxes[b]: have[c] = true; if canOpen[c] and not opened[c], open and enqueue it.
Step 4: Return total.
Time: O(n + total keys + total contained boxes). Space: O(n).
What Trips People Up in Real Interviews
Only enqueueing boxes when you find them. A locked box you already hold must be enqueued later when its key shows up.
Opening a box twice — once when its key appears and once when the box itself appears. Guard with an opened flag.
Trying to decide an order of openings. Since opening is monotone (it only gives you more), any order reaches the same final state.
Forgetting that keys can arrive before the box does.
Solution Code
from collections import deque
def maxCandies(status, candies, keys, containedBoxes, initialBoxes):
n = len(status)
have = [False] * n
can_open = [s == 1 for s in status]
opened = [False] * n
q = deque()
for b in initialBoxes:
have[b] = True
if can_open[b]:
opened[b] = True
q.append(b)
total = 0
while q:
b = q.popleft()
total += candies[b]
for k in keys[b]:
can_open[k] = True
if have[k] and not opened[k]:
opened[k] = True
q.append(k)
for c in containedBoxes[b]:
have[c] = True
if can_open[c] and not opened[c]:
opened[c] = True
q.append(c)
return totalFrequently Asked Questions
What is the Maximum Candies You Can Get from Boxes problem?
Maximum Candies You Can Get from Boxes starts you with some boxes; each box is open or locked, holds candies, keys to other boxes, and other boxes. You can open any box you have that is open or for which you hold a key. How many candies can you collect? It is a BFS where a box becomes usable only once two conditions — "I have it" and "I can open it" — are both true.
How do you solve Maximum Candies You Can Get from Boxes?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Maximum Candies You Can Get from Boxes?
Maximum Candies You Can Get from Boxes is asked at Airbnb. It is a hard difficulty problem.
What are common mistakes on Maximum Candies You Can Get from Boxes?
- Only enqueueing boxes when you find them. A locked box you already hold must be enqueued later when its key shows up.
- Opening a box twice — once when its key appears and once when the box itself appears. Guard with an `opened` flag.
- Trying to decide an order of openings. Since opening is monotone (it only gives you more), any order reaches the same final state.
- Forgetting that keys can arrive before the box does.