1298. Maximum Candies You Can Get from Boxes
Asked at Airbnb
Difficulty
Hard
Time
O(n + total keys + total contain
Space
O(n)
Pattern
Array
Companies
1
Problem
You have n boxes, labeled 0 to n-1. Each box has a status: 1 means it is already open, 0 means it is locked. Each box also holds some candies, a list of keys (labels of boxes those keys unlock), and a list of containedBoxes (other boxes sitting inside it).
You start with a set of boxes given by initialBoxes. You may take the candies from any box you have that is open, or that you hold a key for. When you open a box, you get its candies, plus every key inside it, plus every box inside it. Keys and boxes you collect can then be used to open more boxes.
Return the maximum total number of candies you can collect. Opening a box never hurts you, so the answer is simply the total candies in every box you can eventually reach and unlock.
Boxes, keys and what you can reach
Constraints
- ●
n == status.length == candies.length == keys.length == containedBoxes.length - ●
1 <= n <= 1000 - ●
status[i] is either 0 or 1 - ●
1 <= candies[i] <= 1000 - ●
0 <= keys[i].length <= n - ●
0 <= keys[i][j] < n - ●
All values of keys[i] are unique - ●
0 <= containedBoxes[i].length <= n
Examples
status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]16status = [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]6Asked At
1 companies| 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).
BFS: open a box only when you have it AND can open it
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
O(n + total keys + total contain timefrom 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 runs in O(n + total keys + total contain time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.