? Beginner-Friendly Guide to Solving "Maximum Candies You Can Get from Boxes" | LeetCode 1298(C++ | JavaScript | Python)

[Sascha]

Ever wondered what it’s like to explore a maze of mysterious boxes containing candies, keys, and even more boxes? ??

Welcome to

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.

, 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: 1 if the i-th box is open, 0 if it's locked
  [*]candies: number of candies in box i
  [*]keys: boxes you can unlock using keys found in box i
  [*]containedBoxes: boxes found inside box i
  [*]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

1. BFS/Queue is ideal here as we explore boxes level by level.
2. We can’t open a locked box until we either:

• Already have the key ?
• Find the key in another box
  1. Some boxes contain other boxes, even if they’re locked—so we may revisit them once we find the right key.

?️ Strategy

1. Use a queue to explore all the boxes we can open.
2. Use a set or visited array to keep track of boxes we’ve already opened.
3. 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++!

Источник:

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.