The Maximum Candies You Can Get from Boxes problem requires you to maximize the number of candies you can collect from a set of boxes, given certain rules:
Constraints:
candies: An array where candies[i] is the number of candies in box ikeys: keys[i] is a list of keys inside box icontainedBoxes: containedBoxes[i] is a list of boxes inside box iinitialBoxes: The list of boxes you start withstatus: status[i] is 1 if box i is open, 0 if lockedThe problem is essentially about exploring a graph of boxes, where each box may unlock new boxes or keys to other boxes. The naive approach would be to try every possible sequence of opening boxes, but this quickly becomes infeasible due to the exponential number of possibilities.
To optimize, we can think of this as a Breadth-First Search (BFS) or queue-based exploration: we start with the boxes we have, open those that are unlocked, and as we find keys or new boxes, we add them to our "frontier" of things to process. We must also ensure we do not revisit boxes we've already opened, to avoid cycles or overcounting candies.
The main challenge is to manage the dependencies between boxes and keys efficiently, so that whenever we obtain a new key, we can check if we now have access to a previously locked box.
We solve this problem using a BFS strategy, treating boxes as nodes in a graph. Here's how:
initialBoxes.Design Choices:
queue (FIFO) to process boxes in the order we gain access to them, ensuring we don't miss any accessible boxes.set for opened boxes ensures we don't double-count candies or get stuck in cycles.set for keys provides O(1) lookup for unlocking boxes as soon as we get the key.
Example:
Suppose:
candies = [1, 0, 5, 2]status = [1, 0, 1, 0]keys = [[], [2], [], []]containedBoxes = [[1,2], [3], [], []]initialBoxes = [0]If you get a key during the process, you revisit any boxes that were previously locked but now can be opened.
Brute-force approach: Would try every possible order of opening boxes, which is exponential: O(2^n) for n boxes.
Optimized BFS approach:
Thus, our approach is efficient and scales linearly with the number of boxes.
We modeled the problem as a graph traversal, using BFS to systematically explore boxes as we unlock them. By tracking opened boxes and available keys, we ensure we never double-count or get stuck. The solution is efficient, elegant, and leverages classic data structures (queue and set) to manage dependencies and maximize the number of candies collected.
from collections import deque
class Solution:
def maxCandies(self, status, candies, keys, containedBoxes, initialBoxes):
n = len(status)
queue = deque(initialBoxes)
has_key = set()
opened = set()
boxes = set(initialBoxes)
res = 0
while queue:
size = len(queue)
progress = False
for _ in range(size):
box = queue.popleft()
if box in opened:
continue
if status[box] == 1 or box in has_key:
res += candies[box]
opened.add(box)
# Add any keys found
for k in keys[box]:
if k not in has_key:
has_key.add(k)
if k in boxes and k not in opened:
queue.append(k)
# Add any contained boxes
for b in containedBoxes[box]:
if b not in boxes:
boxes.add(b)
queue.append(b)
progress = True
else:
queue.append(box) # Try again later
if not progress:
break # No new boxes opened this round, so stop
return res
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
class 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();
queue<int> q;
unordered_set<int> hasKey, opened, boxes;
int res = 0;
for (int b : initialBoxes) {
q.push(b);
boxes.insert(b);
}
while (!q.empty()) {
int size = q.size();
bool progress = false;
for (int i = 0; i < size; ++i) {
int box = q.front(); q.pop();
if (opened.count(box)) continue;
if (status[box] == 1 || hasKey.count(box)) {
res += candies[box];
opened.insert(box);
for (int k : keys[box]) {
if (!hasKey.count(k)) {
hasKey.insert(k);
if (boxes.count(k) && !opened.count(k))
q.push(k);
}
}
for (int b : containedBoxes[box]) {
if (!boxes.count(b)) {
boxes.insert(b);
q.push(b);
}
}
progress = true;
} else {
q.push(box);
}
}
if (!progress) break;
}
return res;
}
};
import java.util.*;
class Solution {
public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
int n = status.length;
Queue<Integer> queue = new LinkedList<>();
Set<Integer> hasKey = new HashSet<>();
Set<Integer> opened = new HashSet<>();
Set<Integer> boxes = new HashSet<>();
int res = 0;
for (int b : initialBoxes) {
queue.offer(b);
boxes.add(b);
}
while (!queue.isEmpty()) {
int size = queue.size();
boolean progress = false;
for (int i = 0; i < size; i++) {
int box = queue.poll();
if (opened.contains(box)) continue;
if (status[box] == 1 || hasKey.contains(box)) {
res += candies[box];
opened.add(box);
for (int k : keys[box]) {
if (!hasKey.contains(k)) {
hasKey.add(k);
if (boxes.contains(k) && !opened.contains(k))
queue.offer(k);
}
}
for (int b : containedBoxes[box]) {
if (!boxes.contains(b)) {
boxes.add(b);
queue.offer(b);
}
}
progress = true;
} else {
queue.offer(box);
}
}
if (!progress) break;
}
return res;
}
}
/**
* @param {number[]} status
* @param {number[]} candies
* @param {number[][]} keys
* @param {number[][]} containedBoxes
* @param {number[]} initialBoxes
* @return {number}
*/
var maxCandies = function(status, candies, keys, containedBoxes, initialBoxes) {
const n = status.length;
const queue = [...initialBoxes];
const hasKey = new Set();
const opened = new Set();
const boxes = new Set(initialBoxes);
let res = 0;
while (queue.length) {
let size = queue.length;
let progress = false;
for (let i = 0; i < size; i++) {
let box = queue.shift();
if (opened.has(box)) continue;
if (status[box] === 1 || hasKey.has(box)) {
res += candies[box];
opened.add(box);
for (let k of keys[box]) {
if (!hasKey.has(k)) {
hasKey.add(k);
if (boxes.has(k) && !opened.has(k)) {
queue.push(k);
}
}
}
for (let b of containedBoxes[box]) {
if (!boxes.has(b)) {
boxes.add(b);
queue.push(b);
}
}
progress = true;
} else {
queue.push(box);
}
}
if (!progress) break;
}
return res;
};