Maximum Candies You Can Get from Boxes

hard graphs bfs queue simulation

Problem

You start with some boxes. Each box may be open or closed and holds some candies, a list of keys to other boxes, and a list of inner boxes. You may take candies from any box you can open, use its keys to unlock other boxes you hold, and add its inner boxes to your collection. A box you hold but cannot open yet is set aside until a matching key arrives. Return the maximum number of candies you can collect.

Inputstatus = [1,0,1,0], candies = [7,5,4,100]

keys = [[],[],[1],[]], contained = [[1,2],[3],[],[]], initial = [0]

Output16

Open box 0 (+7, find boxes 1,2). Box 1 is locked. Open box 2 (+4, find key to 1). Now open box 1 (+5, find box 3, still locked). Total = 7 + 4 + 5 = 16.

status (0/1, comma-separated)

candies (comma-separated)

keys (box lists, ';'-separated)

contained boxes (lists, ';'-separated)

initialBoxes (comma-separated)

def max_candies(status, candies, keys, contained, initial):
    have = set(initial)            # boxes we physically hold
    have_key = set(i for i, s in enumerate(status) if s == 1)
    queue = [b for b in initial if b in have_key]
    seen = set(queue)              # boxes already opened
    total = 0
    while queue:
        b = queue.pop(0)           # open box b
        total += candies[b]
        for k in keys[b]:          # keys unlock other boxes
            have_key.add(k)
            if k in have and k not in seen:
                seen.add(k); queue.append(k)
        for c in contained[b]:     # inner boxes we now hold
            have.add(c)
            if c in have_key and c not in seen:
                seen.add(c); queue.append(c)
    return total

function maxCandies(status, candies, keys, contained, initial) {
  const have = new Set(initial);
  const haveKey = new Set();
  status.forEach((s, i) => { if (s === 1) haveKey.add(i); });
  const queue = initial.filter(b => haveKey.has(b));
  const seen = new Set(queue);
  let total = 0;
  while (queue.length) {
    const b = queue.shift();
    total += candies[b];
    for (const k of keys[b]) {
      haveKey.add(k);
      if (have.has(k) && !seen.has(k)) { seen.add(k); queue.push(k); }
    }
    for (const c of contained[b]) {
      have.add(c);
      if (haveKey.has(c) && !seen.has(c)) { seen.add(c); queue.push(c); }
    }
  }
  return total;
}

int maxCandies(int[] status, int[] candies, int[][] keys, int[][] contained, int[] initial) {
    Set<Integer> have = new HashSet<>(), haveKey = new HashSet<>(), seen = new HashSet<>();
    Queue<Integer> queue = new ArrayDeque<>();
    for (int b : initial) have.add(b);
    for (int i = 0; i < status.length; i++) if (status[i] == 1) haveKey.add(i);
    for (int b : initial) if (haveKey.contains(b)) { seen.add(b); queue.add(b); }
    int total = 0;
    while (!queue.isEmpty()) {
        int b = queue.poll();
        total += candies[b];
        for (int k : keys[b]) {
            haveKey.add(k);
            if (have.contains(k) && seen.add(k)) queue.add(k);
        }
        for (int c : contained[b]) {
            have.add(c);
            if (haveKey.contains(c) && seen.add(c)) queue.add(c);
        }
    }
    return total;
}

int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys,
               vector<vector<int>>& contained, vector<int>& initial) {
    set<int> have(initial.begin(), initial.end()), haveKey, seen;
    queue<int> q;
    for (int i = 0; i < (int)status.size(); i++) if (status[i] == 1) haveKey.insert(i);
    for (int b : initial) if (haveKey.count(b)) { seen.insert(b); q.push(b); }
    int total = 0;
    while (!q.empty()) {
        int b = q.front(); q.pop();
        total += candies[b];
        for (int k : keys[b]) {
            haveKey.insert(k);
            if (have.count(k) && !seen.count(k)) { seen.insert(k); q.push(k); }
        }
        for (int c : contained[b]) {
            have.insert(c);
            if (haveKey.count(c) && !seen.count(c)) { seen.insert(c); q.push(c); }
        }
    }
    return total;
}

Explanation

This is a BFS / graph-traversal simulation. The "nodes" are boxes; the "edges" are the keys and inner-box relationships that let one box unlock or reveal another. The twist is that holding a box is not enough to open it — you also need it to be unlocked.

We track three sets. have is every box we physically hold, haveKey is every box we are allowed to open (it started open, or a key arrived), and seen marks boxes we already pushed onto the queue so we never process one twice. A box becomes processable exactly when it lands in both have and haveKey.

We seed the queue with the initial boxes that are already open. While the queue is non-empty we pop a box, take its candies, and unfold it: each key we find is added to haveKey, and each inner box is added to have. After each addition we check the joint condition — if that box is now both held and unlocked and not yet seen, we enqueue it.

The key insight is that a box we hold but cannot open is simply left in the sets. When the matching key is later discovered, the have.has(k) check fires and the box finally enters the queue. This naturally handles the order-independence: it does not matter whether the box or its key shows up first.

Because each box is enqueued at most once and each key / inner box is scanned once, the whole process is linear in the total input size. The running total when the queue drains is the maximum candies obtainable.

Time: O(n + K) Space: O(n)