# Maximum Candies You Can Get from Boxes
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-candies-you-can-get-from-boxes)
Canonical: https://scaleengineer.com/dsa/problems/maximum-candies-you-can-get-from-boxes
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Graph
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [Lyft](https://scaleengineer.com/companies/lyft)
---
## Problem
You have `n` boxes labeled from `0` to `n - 1`. You are given four arrays: `status`, `candies`, `keys`, and `containedBoxes` where:

* `status[i]` is `1` if the `ith` box is open and `0` if the `ith` box is closed,
* `candies[i]` is the number of candies in the `ith` box,
* `keys[i]` is a list of the labels of the boxes you can open after opening the `ith` box.
* `containedBoxes[i]` is a list of the boxes you found inside the `ith` box.

You are given an integer array `initialBoxes` that contains the labels of the boxes you initially have. You can take all the candies in **any open box** and you can use the keys in it to open new boxes and you also can use the boxes you find in it.

Return _the maximum number of candies you can get following the rules above_.

**Example 1:**

**Input:** status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]
**Output:** 16
**Explanation:** You will be initially given box 0. You will find 7 candies in it and boxes 1 and 2.
Box 1 is closed and you do not have a key for it so you will open box 2. You will find 4 candies and a key to box 1 in box 2.
In box 1, you will find 5 candies and box 3 but you will not find a key to box 3 so box 3 will remain closed.
Total number of candies collected = 7 + 4 + 5 = 16 candy.

**Example 2:**

**Input:** status = [1,0,0,0,0,0], candies = [1,1,1,1,1,1], keys = [[1,2,3,4,5],[],[],[],[],[]], containedBoxes = [[1,2,3,4,5],[],[],[],[],[]], initialBoxes = [0]
**Output:** 6
**Explanation:** You have initially box 0. Opening it you can find boxes 1,2,3,4 and 5 and their keys.
The total number of candies will be 6.

**Constraints:**

* `n == status.length == candies.length == keys.length == containedBoxes.length`
* `1 <= n <= 1000`
* `status[i]` is either `0` or `1`.
* `1 <= candies[i] <= 1000`
* `0 <= keys[i].length <= n`
* `0 <= keys[i][j] < n`
* All values of `keys[i]` are **unique**.
* `0 <= containedBoxes[i].length <= n`
* `0 <= containedBoxes[i][j] < n`
* All values of `containedBoxes[i]` are unique.
* Each box is contained in one box at most.
* `0 <= initialBoxes.length <= n`
* `0 <= initialBoxes[i] < n`

# Approaches
## Iterative Simulation with Repeated Scans
This approach simulates the process of opening boxes iteratively. In each iteration, it scans through all the boxes we currently possess to find any that are open and haven't been processed yet. If any such boxes are found, they are "opened": we collect their candies, use their keys to open other boxes, and collect the boxes contained within them. This process repeats until an entire iteration passes without any new box being opened, signifying that no more candies can be collected.
**Time:** O(N^2 + K + C), where N is the number of boxes, K is the total number of keys, and C is the total number of contained boxes. The outer loop can run up to N times, and the inner loop also runs N times, leading to an O(N^2) component for scanning. The processing of all keys and contained boxes contributes O(K+C) over the entire execution. · **Space:** O(N) for the `hasBox` and `opened` boolean arrays.
**Pros:** Simple to conceptualize and implement.; Correctly solves the problem by repeatedly attempting to make progress until no more boxes can be opened.
**Cons:** Inefficient due to repeated scanning of all `n` boxes in each iteration of the main loop.; The time complexity is quadratic in the number of boxes, which can be slow for larger inputs.
### Explanation
We use a boolean array `hasBox` to keep track of which boxes we possess, initialized from `initialBoxes`. We also use a boolean array `opened` to track which boxes have already been processed.

The core of the algorithm is a `while` loop that continues as long as we can make progress. A flag, `openedNewBoxInLoop`, tracks if any box was opened in the current iteration.

Inside the loop, we iterate from box `0` to `n-1`. If we have the box (`hasBox[i]`), it's open (`status[i] == 1`), and we haven't opened it yet (`!opened[i]`), we process it.

Processing a box involves:
1.  Adding its candies to the total.
2.  Marking it as opened.
3.  Setting the `openedNewBoxInLoop` flag to true.
4.  For every key found, updating the `status` of the corresponding box to open.
5.  For every contained box, marking it as possessed in our `hasBox` array.

If the loop completes an entire pass over all `n` boxes without opening a new one (`openedNewBoxInLoop` remains false), we break out and return the total candies collected. This approach is straightforward but inefficient due to the repeated scanning.

```java
class Solution {
    public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
        int n = status.length;
        boolean[] hasBox = new boolean[n];
        for (int box : initialBoxes) {
            hasBox[box] = true;
        }

        boolean[] opened = new boolean[n];
        int totalCandies = 0;

        while (true) {
            boolean openedNewBoxInLoop = false;
            for (int i = 0; i < n; i++) {
                if (hasBox[i] && status[i] == 1 && !opened[i]) {
                    // Open the box
                    totalCandies += candies[i];
                    opened[i] = true;
                    openedNewBoxInLoop = true;

                    // Use keys
                    for (int key : keys[i]) {
                        status[key] = 1;
                    }

                    // Collect contained boxes
                    for (int box : containedBoxes[i]) {
                        hasBox[box] = true;
                    }
                }
            }
            if (!openedNewBoxInLoop) {
                break;
            }
        }
        return totalCandies;
    }
}
```
### Algorithm
- Initialize `totalCandies = 0`.
- Initialize a boolean array `hasBox` of size `n`. Mark `hasBox[i] = true` for all `i` in `initialBoxes`.
- Initialize a boolean array `opened` of size `n` to all `false`.
- Start a loop that continues indefinitely (`while(true)`).
- Inside the loop, initialize a boolean `openedNewBoxInLoop = false`.
- Iterate through all boxes `i` from `0` to `n-1`.
- If `hasBox[i]` is true, `status[i]` is 1, and `opened[i]` is false:
    - Add `candies[i]` to `totalCandies`.
    - Set `opened[i] = true`.
    - Set `openedNewBoxInLoop = true`.
    - For each `key` in `keys[i]`, set `status[key] = 1`.
    - For each `containedBox` in `containedBoxes[i]`, set `hasBox[containedBox] = true`.
- After the inner loop, if `openedNewBoxInLoop` is false, break the outer loop.
- Return `totalCandies`.

## Optimized Traversal using Breadth-First Search (BFS)
This approach models the problem as a graph traversal and uses a Breadth-First Search (BFS) algorithm for an efficient solution. We maintain a queue of boxes that are both possessed and open. We start by populating this queue with any initial boxes that are already open. Then, we process boxes from the queue one by one. When we open a box, we collect its candies, and any new keys or contained boxes we find can potentially unlock or give us access to more boxes, which are then added to the queue if they are open. This avoids redundant checks and ensures each box is processed at most once.
**Time:** O(N + I + K + C), where `N` is the number of boxes, `I` is the number of initial boxes, `K` is the total number of keys, and `C` is the total number of contained boxes. Each box is processed at most once, and each key and contained box is considered once, leading to a linear time complexity. · **Space:** O(N) to store the `hasBox` and `visited` arrays, and for the queue which can hold up to `N` boxes in the worst case.
**Pros:** Highly efficient, with a linear time complexity relative to the input size.; Avoids redundant work by processing each box and its contents only once.; It's a standard and robust graph traversal algorithm.
**Cons:** Slightly more complex to implement than the naive simulation due to the use of a queue and multiple state-tracking arrays.
### Explanation
The core idea is to only consider boxes that we can act upon immediately. A queue is a perfect data structure for this, holding the set of "openable" boxes.

We use a boolean array `hasBox` to track the boxes we possess and a boolean array `visited` to ensure we don't process a box more than once.

First, we initialize `hasBox` for all `initialBoxes`. We then check these initial boxes: if a box is already open (`status[i] == 1`), we add it to our queue of boxes to process and mark it as visited to avoid re-adding it.

The main BFS loop runs as long as the queue is not empty. In each step, we dequeue a box.

For the dequeued box, we:
1.  Add its candies to our total.
2.  Process the keys it contains. For each key, we update the corresponding box's status to open. If we already possess this newly unlocked box (`hasBox` is true) and haven't visited it, we add it to the queue.
3.  Process the boxes it contains. For each contained box, we mark it as possessed (`hasBox` becomes true). If this newly acquired box is already open (`status` is 1) and we haven't visited it, we add it to the queue.

This process continues until the queue is empty, meaning there are no more boxes we can open. This method is much more efficient as it processes each component (box, key, contained box) only a constant number of times.

```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
        int n = status.length;
        boolean[] hasBox = new boolean[n];
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new LinkedList<>();

        for (int box : initialBoxes) {
            hasBox[box] = true;
            if (status[box] == 1) {
                q.offer(box);
                visited[box] = true;
            }
        }

        int totalCandies = 0;
        while (!q.isEmpty()) {
            int currentBox = q.poll();
            totalCandies += candies[currentBox];

            // Use keys to open other boxes
            for (int key : keys[currentBox]) {
                if (status[key] == 0) { // If the box was closed
                    status[key] = 1;
                    // If we have this box and it hasn't been visited, add to queue
                    if (hasBox[key] && !visited[key]) {
                        q.offer(key);
                        visited[key] = true;
                    }
                }
            }

            // Collect contained boxes
            for (int containedBox : containedBoxes[currentBox]) {
                hasBox[containedBox] = true;
                // If the newly found box is open and not visited, add to queue
                if (status[containedBox] == 1 && !visited[containedBox]) {
                    q.offer(containedBox);
                    visited[containedBox] = true;
                }
            }
        }

        return totalCandies;
    }
}
```
### Algorithm
- Initialize `totalCandies = 0`.
- Initialize a queue `q`.
- Initialize a boolean array `visited` of size `n` to all `false`.
- Initialize a boolean array `hasBox` of size `n` to all `false`.
- For each `box` in `initialBoxes`, set `hasBox[box] = true`.
- For each `box` in `initialBoxes`, if `status[box] == 1`, add `box` to `q` and set `visited[box] = true`.
- While `q` is not empty:
    - Dequeue a box `b`.
    - Add `candies[b]` to `totalCandies`.
    - For each `key` in `keys[b]`:
        - Set `status[key] = 1`.
        - If `hasBox[key]` is true and `visited[key]` is false, add `key` to `q` and set `visited[key] = true`.
    - For each `containedBox` in `containedBoxes[b]`:
        - Set `hasBox[containedBox] = true`.
        - If `status[containedBox]` is 1 and `visited[containedBox]` is false, add `containedBox` to `q` and set `visited[containedBox] = true`.
- Return `totalCandies`.

# Solutions
### Java

```java
class Solution {
public
  int maxCandies(int[] status, int[] candies, int[][] keys,
                 int[][] containedBoxes, int[] initialBoxes) {
    int ans = 0;
    int n = status.length;
    boolean[] has = new boolean[n];
    boolean[] took = new boolean[n];
    Deque<Integer> q = new ArrayDeque<>();
    for (int i : initialBoxes) {
      has[i] = true;
      if (status[i] == 1) {
        ans += candies[i];
        took[i] = true;
        q.offer(i);
      }
    }
    while (!q.isEmpty()) {
      int i = q.poll();
      for (int k : keys[i]) {
        status[k] = 1;
        if (has[k] && !took[k]) {
          ans += candies[k];
          took[k] = true;
          q.offer(k);
        }
      }
      for (int j : containedBoxes[i]) {
        has[j] = true;
        if (status[j] == 1 && !took[j]) {
          ans += candies[j];
          took[j] = true;
          q.offer(j);
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxCandies(vector<int> &status, vector<int> &candies,
                 vector<vector<int>> &keys, vector<vector<int>> &containedBoxes,
                 vector<int> &initialBoxes) {
    int ans = 0;
    int n = status.size();
    vector<bool> has(n);
    vector<bool> took(n);
    queue<int> q;
    for (int &i : initialBoxes) {
      has[i] = true;
      if (status[i]) {
        ans += candies[i];
        took[i] = true;
        q.push(i);
      }
    }
    while (!q.empty()) {
      int i = q.front();
      q.pop();
      for (int k : keys[i]) {
        status[k] = 1;
        if (has[k] && !took[k]) {
          ans += candies[k];
          took[k] = true;
          q.push(k);
        }
      }
      for (int j : containedBoxes[i]) {
        has[j] = true;
        if (status[j] && !took[j]) {
          ans += candies[j];
          took[j] = true;
          q.push(j);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int], ) -> int: q = deque([i for i in initialBoxes if status[i] == 1]) ans = sum(candies[i] for i in initialBoxes if status[i] == 1) has = set(initialBoxes) took = {i for i in initialBoxes if status[i] == 1} while q: i = q . popleft() for k in keys[i]: status[k] = 1 if k in has and k not in took: ans += candies[k] took . add(k) q . append(k) for j in containedBoxes[i]: has . add(j) if status[j] and j not in took: ans += candies[j] took . add(j) q . append(j) return ans

```