Maximum Candies You Can Get from Boxes

Hard

#1209Time: 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.2 companies

Algorithms

Breadth-First Search

Data structures

Array Graph

Companies

Airbnb Lyft

Prompt

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 i^th box is open and 0 if the i^th box is closed,
candies[i] is the number of candies in the i^th box,
keys[i] is a list of the labels of the boxes you can open after opening the i^th box.
containedBoxes[i] is a list of the boxes you found inside the i^th 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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

Adding its candies to the total.
Marking it as opened.
Setting the openedNewBoxInLoop flag to true.
For every key found, updating the status of the corresponding box to open.
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.

1class Solution {2    public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {3        int n = status.length;4        boolean[] hasBox = new boolean[n];5        for (int box : initialBoxes) {6            hasBox[box] = true;7        }8 9        boolean[] opened = new boolean[n];10        int totalCandies = 0;11 12        while (true) {13            boolean openedNewBoxInLoop = false;14            for (int i = 0; i < n; i++) {15                if (hasBox[i] && status[i] == 1 && !opened[i]) {16                    // Open the box17                    totalCandies += candies[i];18                    opened[i] = true;19                    openedNewBoxInLoop = true;20 21                    // Use keys22                    for (int key : keys[i]) {23                        status[key] = 1;24                    }25 26                    // Collect contained boxes27                    for (int box : containedBoxes[i]) {28                        hasBox[box] = true;29                    }30                }31            }32            if (!openedNewBoxInLoop) {33                break;34            }35        }36        return totalCandies;37    }38}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

Add its candies to our total.
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.
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.

1import java.util.LinkedList;2import java.util.Queue;3 4class Solution {5    public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {6        int n = status.length;7        boolean[] hasBox = new boolean[n];8        boolean[] visited = new boolean[n];9        Queue<Integer> q = new LinkedList<>();10 11        for (int box : initialBoxes) {12            hasBox[box] = true;13            if (status[box] == 1) {14                q.offer(box);15                visited[box] = true;16            }17        }18 19        int totalCandies = 0;20        while (!q.isEmpty()) {21            int currentBox = q.poll();22            totalCandies += candies[currentBox];23 24            // Use keys to open other boxes25            for (int key : keys[currentBox]) {26                if (status[key] == 0) { // If the box was closed27                    status[key] = 1;28                    // If we have this box and it hasn't been visited, add to queue29                    if (hasBox[key] && !visited[key]) {30                        q.offer(key);31                        visited[key] = true;32                    }33                }34            }35 36            // Collect contained boxes37            for (int containedBox : containedBoxes[currentBox]) {38                hasBox[containedBox] = true;39                // If the newly found box is open and not visited, add to queue40                if (status[containedBox] == 1 && !visited[containedBox]) {41                    q.offer(containedBox);42                    visited[containedBox] = true;43                }44            }45        }46 47        return totalCandies;48    }49}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int maxCandies(int[] status, int[] candies, int[][] keys,4                 int[][] containedBoxes, int[] initialBoxes) {5    int ans = 0;6    int n = status.length;7    boolean[] has = new boolean[n];8    boolean[] took = new boolean[n];9    Deque<Integer> q = new ArrayDeque<>();10    for (int i : initialBoxes) {11      has[i] = true;12      if (status[i] == 1) {13        ans += candies[i];14        took[i] = true;15        q.offer(i);16      }17    }18    while (!q.isEmpty()) {19      int i = q.poll();20      for (int k : keys[i]) {21        status[k] = 1;22        if (has[k] && !took[k]) {23          ans += candies[k];24          took[k] = true;25          q.offer(k);26        }27      }28      for (int j : containedBoxes[i]) {29        has[j] = true;30        if (status[j] == 1 && !took[j]) {31          ans += candies[j];32          took[j] = true;33          q.offer(j);34        }35      }36    }37    return ans;38  }39}

1class Solution {2public:3  int maxCandies(vector<int> &status, vector<int> &candies,4                 vector<vector<int>> &keys, vector<vector<int>> &containedBoxes,5                 vector<int> &initialBoxes) {6    int ans = 0;7    int n = status.size();8    vector<bool> has(n);9    vector<bool> took(n);10    queue<int> q;11    for (int &i : initialBoxes) {12      has[i] = true;13      if (status[i]) {14        ans += candies[i];15        took[i] = true;16        q.push(i);17      }18    }19    while (!q.empty()) {20      int i = q.front();21      q.pop();22      for (int k : keys[i]) {23        status[k] = 1;24        if (has[k] && !took[k]) {25          ans += candies[k];26          took[k] = true;27          q.push(k);28        }29      }30      for (int j : containedBoxes[i]) {31        has[j] = true;32        if (status[j] && !took[j]) {33          ans += candies[j];34          took[j] = true;35          q.push(j);36        }37      }38    }39    return ans;40  }41};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem