Maximum Candies You Can Get from Boxes - Solution & Explanation

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.