Ever wondered what itโs like to explore a maze of mysterious boxes containing candies, keys, and even more boxes? ๐๐ฌ
Welcome to LeetCode 1298 โ Maximum Candies You Can Get from Boxes, a fun graph traversal problem that will help you sharpen your BFS skills while reasoning through dependencies.
In this guide, we'll break down the problem, explain the optimal strategy, and implement the solution in C++, JavaScript (ES6+), and Pythonโperfect for learners at any level ๐.
๐ Problem Statement
You are given:
-
status[i]
: 1 if thei
-th box is open, 0 if it's locked -
candies[i]
: number of candies in boxi
-
keys[i]
: boxes you can unlock using keys found in boxi
-
containedBoxes[i]
: boxes found inside boxi
-
initialBoxes
: the boxes you initially have access to
Your task is to maximize the number of candies you can collect by strategically opening boxes and using the keys.
๐ง Key Observations
- BFS/Queue is ideal here as we explore boxes level by level.
- We canโt open a locked box until we either:
- Already have the key ๐
- Find the key in another box
- Some boxes contain other boxes, even if theyโre lockedโso we may revisit them once we find the right key.
๐บ๏ธ Strategy
- Use a queue to explore all the boxes we can open.
- Use a set or visited array to keep track of boxes weโve already opened.
- For every box:
- Collect candies
- Add found keys to a
keySet
- Add new contained boxes to our queue
- If a previously locked box becomes unlockable (due to a new key), revisit it
๐ง Code Implementations
โ JavaScript (ES6+)
const maxCandies = (status, candies, keys, containedBoxes, initialBoxes) => {
const visited = new Array(status.length).fill(false);
const haveKey = new Set();
const toOpen = new Set(initialBoxes);
const queue = [...initialBoxes];
let total = 0;
while (queue.length) {
const box = queue.shift();
if (visited[box] || (!status[box] && !haveKey.has(box))) continue;
visited[box] = true;
total += candies[box];
for (const key of keys[box]) {
haveKey.add(key);
if (toOpen.has(key) && !visited[key]) queue.push(key);
}
for (const contained of containedBoxes[box]) {
toOpen.add(contained);
if (!visited[contained]) queue.push(contained);
}
}
return total;
};
โ Python
from collections import deque
def maxCandies(status, candies, keys, containedBoxes, initialBoxes):
n = len(status)
visited = [False] * n
key_set = set()
to_open = set(initialBoxes)
queue = deque(initialBoxes)
total = 0
while queue:
box = queue.popleft()
if visited[box] or (status[box] == 0 and box not in key_set):
continue
visited[box] = True
total += candies[box]
for key in keys[box]:
key_set.add(key)
if key in to_open and not visited[key]:
queue.append(key)
for new_box in containedBoxes[box]:
to_open.add(new_box)
if not visited[new_box]:
queue.append(new_box)
return total
โ C++
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
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<bool> visited(n, false);
unordered_set<int> haveKey;
unordered_set<int> toOpen(initialBoxes.begin(), initialBoxes.end());
queue<int> q;
for (int box : initialBoxes) q.push(box);
while (!q.empty()) {
int box = q.front(); q.pop();
if (visited[box] || (status[box] == 0 && haveKey.find(box) == haveKey.end()))
continue;
visited[box] = true;
total += candies[box];
for (int key : keys[box]) {
haveKey.insert(key);
if (toOpen.count(key) && !visited[key]) q.push(key);
}
for (int contained : containedBoxes[box]) {
toOpen.insert(contained);
if (!visited[contained]) q.push(contained);
}
}
return total;
}
๐งช Sample Test Case โ Realistic and Complex
status = [1,1,0,1,1,0,0,1,0,0,1,1,0,0,0,0,1,0,1,1,0,0,0,0,1,0,0,0,1,0,0,1,1,1,1,1,0,1,1,0,1,1,1,1,0,0,1,0,0]
candies = [732,320,543,300,814,568,947,685,142,111,805,233,813,306,55,1,290,944,36,592,150,596,372,299,644,445,605,202,64,807,753,731,552,766,119,862,453,136,43,572,801,518,936,408,515,215,492,738,154]
keys = [[42,2,24,8,39,16,46],[20,39,46,21,32,31,43,16,12,23,3],[21,14,30,2,11,13,27,37,4,48],[16,17,15,6],[31,14,3,32,35,19,42,43,44,29,25,41],[7,39,2,3,40,28,37,35,43,22,6,23,48,10,21,11],[27,1,37,3,45,32,30,26,16,2,35,19,31,47,5,14],[28,35,23,17,6],[6,39,34,22],[44,29,36,31,40,22,9,11,17,25,1,14,41],[39,37,11,36,17,42,13,12,7,9,43,41],[23,16,32,37],[36,39,21,41],[15,27,5,42],[11,5,18,48,25,47,17,0,41,26,9,29],[18,36,40,35,12,33,11,5,44,14,46,7],[48,22,11,33,14],[44,12,3,31,25,15,18,28,42,43],[36,9,0,42],[1,22,3,24,9,11,43,8,35,5,41,29,40],[15,47,32,28,33,31,4,43],[1,11,6,37,28],[46,20,47,32,26,15,11,40],[33,45,26,40,12,3,16,18,10,28,5],[14,6,4,46,34,9,33,24,30,12,37],[45,24,18,31,32,39,26,27],[29,0,32,15,7,48,36,26,33,31,18,39,23,34,44],[25,16,42,31,41,35,26,10,3,1,4,29],[8,11,5,40,9,18,10,16,26,30,19,2,14,4],[],[0,20,17,47,41,36,23,42,15,13,27],[7,15,44,38,41,42,26,19,5,47],[],[37,22],[21,24,15,48,33,6,39,11],[23,7,3,29,10,40,1,16,6,8,27],[27,29,25,26,46,15,16],[33,40,10,38,13,19,17,23,32,39,7],[35,3,39,18],[47,11,27,23,35,26,43,4,22,38,44,31,1,0],[],[18,43,46,9,15,3,42,31,13,4,12,39,22],[42,45,47,18,26,41,38,9,0,35,8,16,29,36,31],[3,20,29,12,46,41,23,4,9,27],[19,33],[32,18],[17,28,7,35,6,22,4,43],[41,31,20,28,35,32,24,23,0,33,18,39,29,30,16],[43,47,46]]
containedBoxes = [[14],[],[26],[4,47],[],[6],[39,43,46],[30],[],[],[0,3],[],[],[],[],[27],[],[],[],[],[12],[],[],[41],[],[31],[20,29],[13,35],[18],[10,40],[],[38],[],[],[19],[5],[],[],[11],[1],[15],[],[],[],[24],[],[],[],[]]
initialBoxes = [2,7,8,9,16,17,21,22,23,25,28,32,33,34,36,37,42,44,45,48]
# Output: 30342
๐ฏ Thatโs over 30,000 candies collectedโproof of how this approach scales to complex graphs with nested dependencies!
๐ Final Thoughts
This problem is a brilliant blend of graph traversal, dependency resolution, and state management. It trains your brain to think in terms of conditions, access rights (keys), and dynamic reachabilityโjust like real-world system design.
๐งโ๐ป Suitable For:
- Beginners exploring BFS
- Intermediate devs brushing up on dependency graphs
- Anyone preparing for interviews at companies that love simulation logic ๐งฉ
๐ฌ Letโs Discuss!
Did you solve it differently? Do you have a cleaner implementation or edge case in mind?
Drop a comment ๐ฌ, leave a โค๏ธ, and follow for more LeetCode deep dives in JavaScript, Python, and C++!
Top comments (6)
Love how you broke this down for BFS and the real-world โaccess rightsโ feeling - super clear across all three languages. Did you run into any edge cases where it got especially tricky with locked boxes?
Thank you so much for the thoughtful feedback! ๐
Yes, I definitely ran into a few edge cases โ especially when we receive a key to a locked box before having the box itself available. Managing that required carefully queuing keys and deferring some actions until all conditions aligned (i.e., we have the box and it's unlocked). ๐ฏ
Handling such scenarios cleanly with BFS and using sets/maps to track available keys and boxes helped a lot. I'm planning to explore that part deeper in a follow-up article too โ appreciate you pointing it out!
Would love to hear how youโd approach those edge cases as well. ๐
there is a CLI named BeB you can use it to create a backend experss and mongodb project in one line try it ๐
Will try it for sure ๐ฌ.
The edge-case handling here is ๐โgreat attention to detail.
Thank you