LeetCode 1298 - Maximum Candies You Can Get from Boxes

Difficulty: 🔴 Hard
Topics: Array, Breadth-First Search, Graph Theory

Solution

Problem Understanding

The problem asks us to determine the maximum number of candies we can collect from a set of boxes with varying accessibility. Each box may be open or closed initially, may contain candies, keys to other boxes, and additional boxes inside it. We start with a set of initial boxes, and we can only open a box if it is either already open or we have obtained a key for it from another box. Once a box is opened, we can take all its candies, acquire its keys, and retrieve any boxes it contains.

The input arrays are status, candies, keys, containedBoxes, and initialBoxes. Each index i corresponds to a box, and its status, candy count, keys, and contained boxes. The output is a single integer representing the total number of candies collected following the rules.

Constraints indicate that n can be up to 1000, the number of candies per box can be up to 1000, and each box may contain multiple keys or boxes, but each box is contained in at most one other box. This ensures that we will not have cycles of boxes inside each other and that BFS or DFS traversal is feasible.

Important edge cases include having all boxes initially closed with no keys available, boxes containing keys to boxes we do not initially have, or chains of boxes where access depends on collecting keys sequentially.

Approaches

A brute-force approach would involve recursively trying all possible sequences of opening boxes and collecting keys. We could model each sequence of actions as a recursive call, trying to open every box we currently have access to, collecting candies, keys, and contained boxes. While correct, this approach is infeasible due to exponential growth in the number of sequences as n grows to 1000.

The key insight for a more optimal solution is to model the problem as a graph traversal with BFS or DFS. Each box can be viewed as a node, and keys or contained boxes provide edges to other nodes. Using a queue and a set to track available boxes, we can iteratively open boxes, collect candies, and add new boxes or keys to our available set. This guarantees that we open every box we have access to in an efficient manner without redundant work.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Try all sequences of opening boxes and collecting keys. Exponential growth.
Optimal BFS/DFS	O(n + m)	O(n + m)	BFS traversal using sets and queues to collect candies and keys efficiently. `m` is total number of keys/boxes across all boxes.

Algorithm Walkthrough

Initialize a queue or set with the initialBoxes we possess.
Maintain a set of keys we currently have and a set of boxes available to open.
Initialize a variable total_candies to 0 to accumulate candies collected.
While there are boxes available to open:
Pick a box from the set.
If the box is open or we have its key, open it.
Add the box’s candies to total_candies.
Add any new keys from this box to our set of keys.
Add any contained boxes to our available boxes set.
Mark the box as opened to prevent revisiting.
Repeat until no more boxes can be opened.
Return total_candies.

Why it works: The BFS/DFS traversal ensures that all boxes accessible via keys and contained boxes are visited exactly once. The invariant is that at any moment, we only attempt to open boxes we have access to either directly or through collected keys, guaranteeing no missed opportunities for collecting candies.

Python Solution

from typing import List
from collections import deque

class Solution:
    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
        available = set(initialBoxes)
        obtained_keys = set()
        opened = set()
        total_candies = 0
        queue = deque(initialBoxes)
        
        while queue:
            box = queue.popleft()
            if box in opened:
                continue
            if status[box] == 1 or box in obtained_keys:
                total_candies += candies[box]
                opened.add(box)
                for key in keys[box]:
                    if key not in obtained_keys:
                        obtained_keys.add(key)
                        if key in available and key not in opened:
                            queue.append(key)
                for contained in containedBoxes[box]:
                    if contained not in opened:
                        queue.append(contained)
                        available.add(contained)
            else:
                queue.append(box)
        
        return total_candies

In this implementation, we maintain a queue for BFS traversal and sets to track opened boxes, available boxes, and obtained keys. Boxes that cannot be opened immediately are re-queued until we eventually collect the necessary keys.

Go Solution

func maxCandies(status []int, candies []int, keys [][]int, containedBoxes [][]int, initialBoxes []int) int {
    available := make(map[int]bool)
    obtainedKeys := make(map[int]bool)
    opened := make(map[int]bool)
    queue := []int{}
    totalCandies := 0

    for _, box := range initialBoxes {
        available[box] = true
        queue = append(queue, box)
    }

    for len(queue) > 0 {
        box := queue[0]
        queue = queue[1:]
        if opened[box] {
            continue
        }
        if status[box] == 1 || obtainedKeys[box] {
            totalCandies += candies[box]
            opened[box] = true
            for _, key := range keys[box] {
                if !obtainedKeys[key] {
                    obtainedKeys[key] = true
                    if available[key] && !opened[key] {
                        queue = append(queue, key)
                    }
                }
            }
            for _, contained := range containedBoxes[box] {
                if !opened[contained] {
                    queue = append(queue, contained)
                    available[contained] = true
                }
            }
        } else {
            queue = append(queue, box)
        }
    }

    return totalCandies
}

The Go implementation mirrors Python logic with maps to track sets, slices for queues, and direct integer accumulation. We handle nil slices naturally as appending to a slice.

Worked Examples

Example 1: status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]

Iteration	Queue	Opened	Obtained Keys	Total Candies
0	[0]	{}	{}	0
1	[1,2]	{0}	{}	7
2	[2]	{0}	{}	7
3	[]	{0,2,1}	{1}	16

Example 2: 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]

Iteration	Queue	Opened	Obtained Keys	Total Candies
0	[0]	{}	{}	0
1	[1,2,3,4,5]	{0}	{1,2,3,4,5}	1
2	[]	{0,1,2,3,4,5}	{1,2,3,4,5}	6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each box and key is processed at most once. `m` is total keys and contained boxes across all boxes.
Space	O(n + m)	Storing opened boxes, available boxes, and keys uses space proportional to boxes and edges.

Since n and m are each ≤ 1000 in the worst case, this algorithm is efficient.

Test Cases

# Provided examples
assert Solution().maxCandies([1,0,1,0],[7,5,4,100],[[],[],[1],[]],[[1,2],[3],[],[]],[0]) == 16
assert Solution().maxCandies([1,0,0,0,0,0],[1,1,1,1,1,1],[[1,2,3,4,5],[],[],[],[],[]],[[1,2,3,4,5],[],[],[],[],[]],[0]) == 6

# Edge cases
assert Solution().maxCandies([0],[10],[[]],[[]],[0]) == 0  # box closed, no keys
assert Solution().maxCandies([1],[10],[[]],[[]],[0]) == 10  # box open
assert Solution().maxCandies([0,0,0],[1,2,