#1298

Hard

auto_awesomeGraph traversal with breadth-first search

LeetCode Problem Workspace

Maximum Candies You Can Get from Boxes

Collect maximum candies from boxes by exploring initially available boxes and using keys to unlock additional ones efficiently.

array breadth first search graph

Problem Statement

You are given n boxes labeled from 0 to n - 1, each with a status indicating if it is open (1) or closed (0). Each box contains a number of candies, possibly keys to other boxes, and other boxes it contains. You are also given an array of initially available boxes.

Your task is to determine the maximum number of candies you can collect by opening boxes you have access to. You may use any keys found to unlock new boxes, and you may use boxes discovered inside other boxes. The goal is to use graph traversal with BFS to systematically explore all boxes that become available, ensuring no box is opened more than once.

Examples

Example 1

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

Output: 16

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

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

Solution Approach

Initialize BFS Queue and Track Accessible Boxes

Start by enqueuing all initially available boxes that are open or for which you have a key. Maintain a set to track visited boxes so that each box is processed exactly once, preventing double-counting of candies.

Process Boxes Iteratively Using BFS

While the queue is not empty, dequeue a box, collect its candies, and add all new keys and contained boxes to the queue if they are now accessible. This BFS ensures you explore boxes layer by layer, respecting the order in which keys make boxes available.

Handle Locked Boxes and Keys Carefully

If a box is locked but you obtain a key from another box, enqueue it for later processing. Continue the BFS until no more boxes can be opened. This prevents missing any reachable boxes and maximizes the candy total.

Complexity Analysis

Metric	Value
Time	O(n^2)
Space	O(n)

Time complexity is O(n^2) because each box may contain keys or boxes leading to nested processing, while space complexity is O(n) to store the visited set, queue, and auxiliary structures for BFS.

What Interviewers Usually Probe

Check if candidate correctly enqueues boxes only when accessible.
Verify they track visited boxes to avoid double counting.
Listen for discussion on BFS versus DFS and reasoning for layer-by-layer exploration.

Common Pitfalls or Variants

Common pitfalls

Forgetting to mark boxes as visited after processing, causing overcounting.
Trying DFS instead of BFS and missing boxes that require keys found later.
Incorrectly handling boxes inside boxes without checking if the key is available.

Follow-up variants

All boxes initially open, emphasizing simple BFS traversal.
Boxes contain keys but no nested boxes, focusing on key handling logic.
Some boxes require multiple keys, testing BFS queuing order and tracking.

FAQ

What is the main approach to solve Maximum Candies You Can Get from Boxes?

Use a breadth-first search (BFS) to explore all boxes you can access, collecting candies and keys in order of availability.

Can DFS be used instead of BFS?

DFS can work but may fail to process boxes in the correct order to use keys effectively; BFS ensures layer-by-layer access.

How do I track which boxes have been opened?

Maintain a visited set to mark boxes as processed, preventing counting the same candies multiple times.

What should I do with keys found in a box?

Add keys to a map or set and enqueue corresponding locked boxes for BFS once the keys are obtained.

What pattern does this problem exemplify?

This problem is a graph traversal pattern using BFS, where nodes are boxes and edges represent access via keys or containment.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

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()
        has, took = set(initialBoxes), set()
        ans = 0

        for box in initialBoxes:
            if status[box]:
                q.append(box)
                took.add(box)
                ans += candies[box]
        while q:
            box = q.popleft()
            for k in keys[box]:
                if not status[k]:
                    status[k] = 1
                    if k in has and k not in took:
                        q.append(k)
                        took.add(k)
                        ans += candies[k]

            for b in containedBoxes[box]:
                has.add(b)
                if status[b] and b not in took:
                    q.append(b)
                    took.add(b)
                    ans += candies[b]
        return ans

Continue Practicing

#1311 get watched videos by your friends #1368 minimum cost to make at least one valid path in a grid #928 minimize malware spread ii