Skip to main content
Talentd

Maximum Candies You Can Get from Boxes - Solution & Explanation

HardArrayBreadth-First SearchGraph19 min readAsked at: Airbnb, Google, Bloomberg +1
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You start with a set of boxes. Some are open, some are locked. Open boxes may contain candies, keys to other boxes, and additional boxes. The task is to collect the maximum number of candies you can access by strategically using keys and opening boxes as they become available.

Approach 1: Breadth-First Search (BFS) Traversal (O(n + m) time, O(n) space)

Model the problem as a traversal over boxes where each box acts like a node in a graph. A box becomes processable when two conditions are satisfied: you possess the box and you have its key (or it is initially open). Use a queue to process boxes as soon as they become accessible. Track three states: boxes you currently have, keys you own, and boxes already opened. When you open a box, collect its candies, add any discovered boxes to your inventory, and store newly found keys. If a key unlocks a box you already have, immediately enqueue it for processing. Each box is processed at most once, so the traversal runs in O(n + m), where n is the number of boxes and m is the total number of keys and contained boxes discovered. Space complexity is O(n) for tracking visited boxes and queues. This approach naturally fits problems involving progressive discovery and is a classic use of Breadth-First Search over a dependency graph.

Approach 2: Depth-First Search (DFS) Exploration (O(n + m) time, O(n) space)

The same dependency structure can be explored using recursive or stack-based DFS. Start from the initial boxes and attempt to open them whenever the key is available. When a box is opened, recursively explore any contained boxes and update the key inventory. If a locked box appears before its key, store it and revisit once the key is discovered. The key insight is that traversal order does not change the final candy count as long as every newly unlocked box is eventually explored. DFS maintains the same complexity bounds: O(n + m) time for processing each box and edge-like relationship once, and O(n) auxiliary space for recursion or stacks. This version frames the problem as a graph reachability task similar to exploring nodes in a graph with conditional access.

Both methods rely on maintaining state about which boxes you possess and which keys unlock them. The problem becomes manageable once you treat boxes and keys as relationships in a traversal structure rather than simulating random opening attempts.

Recommended for interviews: The BFS approach is usually preferred because the queue directly represents boxes that just became accessible. It demonstrates clear reasoning about state transitions and mirrors typical solutions for unlocking dependencies in array-indexed structures. DFS works as well, but BFS tends to be easier to reason about and debug during interviews.

Approach 1: Breadth-First Search (BFS) Approach

This approach uses a queue to process boxes in a breadth-first manner. You begin with the initial boxes, popping them one by one, collecting candies if they are open, and adding contained boxes and keys to respective sets. Keys allow you to open new boxes, which are then also added to the queue for further processing. This ensures all accessible boxes are eventually opened.

Keep track of opened boxes to avoid reprocessing.

Python Implementation

This Python implementation uses a deque (double-ended queue) for efficient popping of elements from the front. By utilizing a set for visited boxes, we ensure that each box is processed only once, even if it is enqueued multiple times due to multiple paths reaching it.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n), where n is the total number of boxes since each box is processed at most once.

Space Complexity: O(n), due to storage of keys, boxes, and visited sets.

Try this approach in the editor →

Approach 2: Depth-First Search (DFS) Approach

This approach involves using a stack to simulate depth-first traversal. Starting with the initial boxes, we push each box onto a stack, popping off the top to explore its contents, collect candies from open boxes, and record newly found keys and contained boxes. Recursive exploration continues as stacks simulate depth-first processing. Each box is processed only when it can be opened, ensuring the solution remains efficient.

C Implementation

The C code uses a simple static array to mimic a stack enabling depth-first processing. The 'opened' Boolean array prevents processing a box multiple times. Efficiency is maintained through iterative use of the stack for DFS.

Code

CJavaScript

C

JavaScript

Complexity

Time Complexity: O(n), as with BFS, each box is visited once.

Space Complexity: O(n), based on the stack and opened array storage.

Try this approach in the editor →

Approach 3: BFS + Hash Set

The problem gives a set of boxes, each of which may have a state (open/closed), candies, keys, and other boxes inside. Our goal is to use the initially given boxes to open as many more boxes as possible and collect the candies inside. We can unlock new boxes by obtaining keys, and get more resources through boxes nested inside other boxes.

We use BFS to simulate the entire exploration process.

We use a queue q to represent the currently accessible and already opened boxes; two sets, has and took, are used to record all boxes we own and boxes we have already processed, to avoid duplicates.

Initially, add all initialBoxes to has. If an initial box is open, immediately add it to the queue q and accumulate its candies.

Then perform BFS, taking boxes out of q one by one:

  • Obtain the keys in the box keys[box] and add any boxes that can be unlocked to the queue;
  • Collect other boxes contained in the box containedBoxes[box]. If a contained box is open and has not been processed, process it immediately;

Each box is processed at most once, and candies are accumulated once. Finally, return the total number of candies ans.

The time complexity is O(n), and the space complexity is O(n), where n is the total number of boxes.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Breadth-First Search (BFS) Approach

Time Complexity: O(n), where n is the total number of boxes since each box is processed at most once.

Space Complexity: O(n), due to storage of keys, boxes, and visited sets.

Depth-First Search (DFS) Approach

Time Complexity: O(n), as with BFS, each box is visited once.

Space Complexity: O(n), based on the stack and opened array storage.

BFS + Hash Set—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Breadth-First Search (BFS)O(n + m)O(n)Best general solution when boxes unlock other boxes progressively
Depth-First Search (DFS)O(n + m)O(n)Useful when implementing recursive exploration of box dependencies

Video Solution

Maximum Candies You Can Get from Boxes | 2 Ways | Simple Intuition | Leetcode 1298 |codestorywithMIK • codestorywithMIK • 8,752 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Candies You Can Get from Boxes easy or hard?
The problem is rated Hard because it requires careful state management between keys, box ownership, and traversal order. Once modeled as a graph traversal problem with BFS or DFS, the logic becomes much clearer.
Maximum Candies You Can Get from Boxes Python/Java solution
Most implementations use BFS with a queue and boolean arrays to track box states. Python commonly uses collections.deque for the queue, while Java uses ArrayDeque or LinkedList. Both follow the same O(n + m) traversal logic.
How to solve Maximum Candies You Can Get from Boxes in O(n)?
Treat boxes as nodes in a graph and traverse them using BFS. Maintain sets for keys, boxes you currently possess, and boxes already opened. Whenever a new key unlocks a box you already have, push it into the queue and continue collecting candies.
What is the best approach for Maximum Candies You Can Get from Boxes?
Breadth-First Search (BFS) is the most practical approach. It processes boxes as soon as they become openable by tracking keys, owned boxes, and visited states. Each box is handled once, giving O(n + m) time complexity where n is the number of boxes and m represents total keys and contained boxes.
Is Maximum Candies You Can Get from Boxes asked at Google/Amazon/Meta?
This type of graph traversal with dependency unlocking appears frequently in interviews at companies like Amazon and Google. The pattern resembles resource unlocking or dependency resolution problems, which are common system and algorithm interview themes.
What data structure is used in Maximum Candies You Can Get from Boxes?
The core data structure is a queue for BFS or a stack/recursion for DFS. Additional arrays or sets track keys obtained, boxes currently owned, and boxes already opened to prevent repeated processing.
What is the time complexity of Maximum Candies You Can Get from Boxes?
The optimal complexity is O(n + m). Each box is opened at most once, and each key or contained box is processed once during traversal. Space complexity is O(n) for tracking visited boxes, owned boxes, and the queue or recursion stack.

Ready to solve this problem?

Practice Maximum Candies You Can Get from Boxes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays