Maximum Candies You Can Get from Boxes solution and explanation

from collections import deque

def maxCandies(status, candies, keys, containedBoxes, initialBoxes):
    available_keys = set()
    box_queue = deque(initialBoxes)
    total_candies = 0
    visited = set()
    
    while box_queue:
        box = box_queue.popleft()
        # Process only if the box has not been visited
        if box not in visited:
            visited.add(box)
            # Check status
            if status[box] == 1 or box in available_keys:
                # Collect candies
                total_candies += candies[box]
                # Add all keys found in this box
                available_keys.update(keys[box])
                # Add all contained boxes to queue
                for containedBox in containedBoxes[box]:
                    box_queue.append(containedBox)
            else:
                # Could not open, add back to queue to try later
                box_queue.append(box)
    
    return total_candies

import java.util.*;

public class Solution {
    public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> availableKeys = new HashSet<>();
        Set<Integer> visited = new HashSet<>();
        int totalCandies = 0;
        
        for (int box : initialBoxes) {
            queue.offer(box);
        }
        
        while (!queue.isEmpty()) {
            int box = queue.poll();
            if (visited.contains(box)) continue;
            visited.add(box);
            
            if (status[box] == 1 || availableKeys.contains(box)) {
                totalCandies += candies[box];
                for (int key : keys[box]) {
                    availableKeys.add(key);
                }
                for (int containedBox : containedBoxes[box]) {
                    queue.offer(containedBox);
                }
            } else {
                queue.offer(box);
            }
        }
        
        return totalCandies;
    }
}

var maxCandies = function(status, candies, keys, containedBoxes, initialBoxes) {
    let totalCandies = 0;
    let openBoxes = new Array(status.length).fill(false);
    let stack = [...initialBoxes];

    while (stack.length > 0) {
        let box = stack.pop();
        // Process box only if not already opened
        if (openBoxes[box]) continue;
        
        if (status[box] === 1) {
            // Mark this box as opened
            openBoxes[box] = true;
            // Add candies
            totalCandies += candies[box];
            // Add keys from this box
            keys[box].forEach((key) => {
                status[key] = 1; // Mark corresponding box as openable
            });
            // Add contained boxes onto the stack
            containedBoxes[box].forEach((containedBox) => {
                stack.push(containedBox);
            });
        } else {
            // If box isn't open, push it back to try later
            stack.push(box);
        }
    }

    return totalCandies;
};

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int maxCandies(int* status, int statusSize, int* candies, int** keys, int keysSize, int* keysColSize, int** containedBoxes, int containedBoxesSize, int* containedBoxesColSize, int* initialBoxes, int initialBoxesSize) {
    int totalCandies = 0;
    bool opened[statusSize];
    for (int i = 0; i < statusSize; ++i) 
        opened[i] = false;
    int stack[statusSize]; 
    int stackSize = 0;

    for (int i = 0; i < initialBoxesSize; ++i) 
        stack[stackSize++] = initialBoxes[i];

    while (stackSize > 0) {
        int box = stack[--stackSize];
        if (opened[box]) 
            continue;
        if (status[box] == 1) {
            opened[box] = true;
            totalCandies += candies[box];
            for (int i = 0; i < keysColSize[box]; ++i) 
                status[keys[box][i]] = 1;
            for (int i = 0; i < containedBoxesColSize[box]; ++i) 
                stack[stackSize++] = containedBoxes[box][i];
        } else {
            stack[stackSize++] = box;
        }
    }

    return totalCandies;
}

class Solution {
public:
    int maxCandies(
        vector<int>& status,
        vector<int>& candies,
        vector<vector<int>>& keys,
        vector<vector<int>>& containedBoxes,
        vector<int>& initialBoxes) {
        queue<int> q;
        unordered_set<int> has, took;
        int ans = 0;

        for (int box : initialBoxes) {
            has.insert(box);
            if (status[box]) {
                q.push(box);
                took.insert(box);
                ans += candies[box];
            }
        }

        while (!q.empty()) {
            int box = q.front();
            q.pop();

            for (int k : keys[box]) {
                if (!status[k]) {
                    status[k] = 1;
                    if (has.count(k) && !took.count(k)) {
                        q.push(k);
                        took.insert(k);
                        ans += candies[k];
                    }
                }
            }

            for (int b : containedBoxes[box]) {
                has.insert(b);
                if (status[b] && !took.count(b)) {
                    q.push(b);
                    took.insert(b);
                    ans += candies[b];
                }
            }
        }

        return ans;
    }
};

function maxCandies(
    status: number[],
    candies: number[],
    keys: number[][],
    containedBoxes: number[][],
    initialBoxes: number[],
): number {
    const q: number[] = [];
    const has: Set<number> = new Set();
    const took: Set<number> = new Set();
    let ans = 0;

    for (const box of initialBoxes) {
        has.add(box);
        if (status[box] === 1) {
            q.push(box);
            took.add(box);
            ans += candies[box];
        }
    }

    while (q.length > 0) {
        const box = q.pop()!;

        for (const k of keys[box]) {
            if (status[k] === 0) {
                status[k] = 1;
                if (has.has(k) && !took.has(k)) {
                    q.push(k);
                    took.add(k);
                    ans += candies[k];
                }
            }
        }

        for (const b of containedBoxes[box]) {
            has.add(b);
            if (status[b] === 1 && !took.has(b)) {
                q.push(b);
                took.add(b);
                ans += candies[b];
            }
        }
    }

    return ans;
}

func maxCandies(status []int, candies []int, keys [][]int, containedBoxes [][]int, initialBoxes []int) (ans int) {
	q := []int{}
	has := make(map[int]bool)
	took := make(map[int]bool)
	for _, box := range initialBoxes {
		has[box] = true
		if status[box] == 1 {
			q = append(q, box)
			took[box] = true
			ans += candies[box]
		}
	}
	for len(q) > 0 {
		box := q[0]
		q = q[1:]
		for _, k := range keys[box] {
			if status[k] == 0 {
				status[k] = 1
				if has[k] && !took[k] {
					q = append(q, k)
					took[k] = true
					ans += candies[k]
				}
			}
		}
		for _, b := range containedBoxes[box] {
			has[b] = true
			if status[b] == 1 && !took[b] {
				q = append(q, b)
				took[b] = true
				ans += candies[b]
			}
		}
	}
	return
}

use std::collections::{HashSet, VecDeque};

impl Solution {
    pub fn max_candies(
        mut status: Vec<i32>,
        candies: Vec<i32>,
        keys: Vec<Vec<i32>>,
        contained_boxes: Vec<Vec<i32>>,
        initial_boxes: Vec<i32>,
    ) -> i32 {
        let mut q: VecDeque<i32> = VecDeque::new();
        let mut has: HashSet<i32> = HashSet::new();
        let mut took: HashSet<i32> = HashSet::new();
        let mut ans = 0;

        for &box_ in &initial_boxes {
            has.insert(box_);
            if status[box_ as usize] == 1 {
                q.push_back(box_);
                took.insert(box_);
                ans += candies[box_ as usize];
            }
        }

        while let Some(box_) = q.pop_front() {
            for &k in &keys[box_ as usize] {
                if status[k as usize] == 0 {
                    status[k as usize] = 1;
                    if has.contains(&k) && !took.contains(&k) {
                        q.push_back(k);
                        took.insert(k);
                        ans += candies[k as usize];
                    }
                }
            }

            for &b in &contained_boxes[box_ as usize] {
                has.insert(b);
                if status[b as usize] == 1 && !took.contains(&b) {
                    q.push_back(b);
                    took.insert(b);
                    ans += candies[b as usize];
                }
            }
        }

        ans
    }
}