1298. Maximum Candies You Can Get from Boxes

Problem Description

You start with an array of boxes, where each box is either open or closed, contains a certain number of candies, may contain keys to other boxes, and might have other boxes inside it. You initially have a set of boxes; these are the ones you can attempt to open if they are not locked. The goal is to collect as many candies as possible by opening boxes (if you can), collecting candies, and using the keys found inside to open new boxes, which in turn can also contain more candies, boxes, and keys.

Specifically:

Each box has a status indicating whether it's open (1) or closed (0).
Each box contains a certain number of candies.
Each box may contain keys that allow you to open other boxes.
Each box may contain other boxes.

You can only collect candies from boxes that are open. If you find a new box within a box, you can attempt to open it either with a key or if it’s already open.

The task is to determine the maximum number of candies you can collect following these rules.

Intuition

To solve this problem, we can use a strategy similar to Breadth-First Search (BFS). BFS is a common approach in graph traversal algorithms which can also be applied to problems like this where there are layers of items to explore (in this case, boxes within boxes).

The main idea behind BFS is to systematically explore the data structures, visiting all neighbors before moving to the next level in the search space. In this problem, this translates to:

Taking all initially available, open boxes.
Collecting all candies from these boxes.
Using all available keys to open any boxes we have.
Exploring all boxes found within these boxes.

To ensure an efficient process, we maintain:

A queue to keep track of all boxes we can open and need to process.
A hash set (has) to keep track of all boxes we have at our disposal, regardless of whether they are open or closed.
A set (took) to keep track of all boxes from which we have already taken candies.

A box is enqueued only if it's open and it has not been processed before, ensuring we don't recount candies or reprocess boxes. We continue this process until there are no more boxes left to open.

By iterating through the boxes in this manner, we guarantee that we've collected all possible candies we can get given the initial conditions.

Learn more about Breadth-First Search and Graph patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Solution Approach

The solution is implemented using a Breadth-First Search (BFS) strategy. Here's a step-by-step breakdown of the approach:

Start by creating a deque (a double-ended queue) called q to hold the indexes of all open boxes we initially have (status[i] == 1) from initialBoxes.
Calculate the starting number of candies by summing up the candies in all initially open boxes. This is stored in an ans variable.
Create a set called has that keeps track of all the boxes we currently have (both open and closed), and another set called took which keeps track of all the boxes from which we've already taken candies.
Start the BFS loop by continuously dequeuing a box index from q as long as q is not empty. For each box index i:

a. Iterate over the list of keys in keys[i], and for each key k: - Set the status of the box with the label k to open (status[k] = 1). - If we have this box (k in has) and we haven't taken candies from it (k not in took), add the number of candies from that box to ans, mark it as took, and append the box index to queue q to process its contents.

b. Iterate over the list of boxes in containedBoxes[i], and for each contained box j: - Add box j to the set has (now we have this box). - If the box j is open (status[j]) and we haven't taken candies from it (j not in took), add the number of candies from that box to ans, mark it as took, and append the box index to queue q to process its contents.
Continue processing until q runs out of boxes. At the end of the BFS loop, ans holds the maximum number of candies that can be collected.

This approach ensures we are efficiently visiting each openable box exactly once and collecting all possible candies by keeping track of the boxes we have and those from which we've already collected candies.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's illustrate the solution approach with a small example:

Suppose we have the following initial setup:

status = [1, 0, 1, 0] means boxes at indices 0 and 2 are initially open.
candies = [7, 5, 3, 4] means the boxes contain 7, 5, 3, and 4 candies, respectively.
keys = [[], [1], [3], []] means box at index 1 has a key to box 1, and box at index 2 has a key to box 3.
containedBoxes = [[2], [3], [], []] means box at index 0 has box 2 inside, and box at index 1 has box 3 inside.
initialBoxes = [0, 1] means we initially have box 0 and 1 in our possession.

Using the solution approach, we proceed with the BFS strategy:

We start by creating a deque q with the open boxes from initialBoxes, which are box 0 and box 1. But since box 1 is closed, we only add box 0 to q: q = deque([0]).
We sum up the candies from initially open boxes, so ans = candies[0] = 7.
We create the sets has = {0, 1} since we have boxes 0 and 1 and took = {0} because we've taken candies from box 0.
We begin the BFS loop:
- Dequeuing box 0 from q, no keys in keys[0] but we have a contained box containedBoxes[0] = [2]. We add box 2 to has, since it's open, add its candies to ans (total now 10), and mark it as took. Now, q = deque([2]).
- Dequeuing box 2 from q, we find a key in keys[2] = [3] that opens box 3. We add candies from box 3 (since it's now open and we have it in has), increasing ans to 14, and add box 3 to took. No contained boxes in box 2, so we continue.
The q is now empty, and the BFS loop ends. ans is 14, which is the maximum number of candies we can collect following the rules.

By keeping track of which boxes we have and from which we've taken candies, along with opening new boxes using the keys we find, we've managed to collect all the candies we possibly could.

Solution Implementation

1from collections import deque
2from typing import List
3
4class Solution:
5    def maxCandies(
6        self,
7        statuses: List[int],  # statuses of boxes (0 for locked, 1 for open)
8        candies: List[int],  # number of candies in each box
9        keys: List[List[int]],  # list of keys for each box
10        containedBoxes: List[List[int]],  # list of boxes contained within each box
11        initialBoxes: List[int],  # list of boxes you start with
12    ) -> int:
13        # Queue with all the open boxes we can go through
14        queue = deque([box for box in initialBoxes if statuses[box] == 1])
15        # Calculate initial number of candies from open boxes
16        total_candies = sum(candies[box] for box in initialBoxes if statuses[box] == 1)
17        # Keep track of all boxes in hand whether they are locked or not
18        boxes_in_hand = set(initialBoxes)
19        # Keep a set of boxes from which candies have been taken
20        boxes_accessed = {box for box in initialBoxes if statuses[box] == 1}
21
22        # Keep iterating while there are boxes in the queue
23        while queue:
24            current_box = queue.popleft()  # Take the first box from the queue
25            # Iterate over the keys contained in the current box
26            for key in keys[current_box]:
27                statuses[key] = 1  # Use the key to open the box with the matching number
28                # Check if the now-opened box is in hand and hasn't been accessed yet
29                if key in boxes_in_hand and key not in boxes_accessed:
30                    total_candies += candies[key]  # Add the candies from the box
31                    boxes_accessed.add(key)  # Mark the box as accessed
32                    queue.append(key)  # Add the box to the queue to process further
33
34            # Iterate over the boxes contained within the current box
35            for box_id in containedBoxes[current_box]:
36                boxes_in_hand.add(box_id)  # Add the contained box to boxes in hand
37                # Check if the box is open and hasn't been accessed yet
38                if statuses[box_id] and box_id not in boxes_accessed:
39                    total_candies += candies[box_id]  # Add candies from the contained box
40                    boxes_accessed.add(box_id)  # Mark the contained box as accessed
41                    queue.append(box_id)  # Add the contained box to the queue for further processing
42
43        # Return the total number of candies collected
44        return total_candies
45

1class Solution {
2  
3    public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
4        int totalCandies = 0; // To keep track of the total number of candies collected
5        int boxCount = status.length; // Number of boxes
6        boolean[] boxHas = new boolean[boxCount]; // Keeps track of whether we have access to a box
7        boolean[] boxOpened = new boolean[boxCount]; // Keeps track of whether we've opened a box
8        Deque<Integer> queue = new ArrayDeque<>(); // Queue to process the boxes to be opened
9      
10        // Initialize by going through the initial boxes
11        for (int boxIndex : initialBoxes) {
12            boxHas[boxIndex] = true; // Mark that we have this box
13            // If we can open it, add its candies and enqueue it for further processing
14            if (status[boxIndex] == 1) {
15                totalCandies += candies[boxIndex];
16                boxOpened[boxIndex] = true;
17                queue.offer(boxIndex);
18            }
19        }
20      
21        // Process the queue while there are boxes to open
22        while (!queue.isEmpty()) {
23            int currentBoxIndex = queue.poll(); // Take the next box from the queue
24          
25            // Process all keys in the current box
26            for (int keyIndex : keys[currentBoxIndex]) {
27                status[keyIndex] = 1; // Change the status to open for the boxes for which we now have keys
28                // If we have not opened the box and now found the key, add candies and enqueue it
29                if (boxHas[keyIndex] && !boxOpened[keyIndex]) {
30                    totalCandies += candies[keyIndex];
31                    boxOpened[keyIndex] = true;
32                    queue.offer(keyIndex);
33                }
34            }
35          
36            // Process all boxes contained inside the current box
37            for (int containedBoxIndex : containedBoxes[currentBoxIndex]) {
38                boxHas[containedBoxIndex] = true; // Mark that we now have this box
39                // If we can open it and haven't before, add candies and enqueue
40                if (status[containedBoxIndex] == 1 && !boxOpened[containedBoxIndex]) {
41                    totalCandies += candies[containedBoxIndex];
42                    boxOpened[containedBoxIndex] = true;
43                    queue.offer(containedBoxIndex);
44                }
45            }
46        }
47      
48        // Return the total candies collected from all boxes we could open
49        return totalCandies;
50    }
51}
52

1class Solution {
2public:
3    int maxCandies(vector<int>& statuses, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
4        int totalCandies = 0; // This will hold the running total of candies collected.
5        int numBoxes = statuses.size(); // Get the number of boxes.
6        vector<bool> hasBox(numBoxes, false); // Tracks if we have a box.
7        vector<bool> openedBox(numBoxes, false); // Tracks if we've opened a box.
8        queue<int> openableBoxes; // Queue to hold boxes that can be opened.
9
10        // Loop over all initially available boxes and try to open them.
11        for (int boxId : initialBoxes) {
12            hasBox[boxId] = true; // We have this box.
13            // If the box is not locked, collect its candies and consider its contents.
14            if (statuses[boxId]) {
15                totalCandies += candies[boxId]; // Add candies from the current box.
16                openedBox[boxId] = true; // Mark the box as opened.
17                openableBoxes.push(boxId); // Add it to the queue of boxes to process.
18            }
19        }
20
21        // Process boxes while there are openable boxes available.
22        while (!openableBoxes.empty()) {
23            int currentBoxId = openableBoxes.front();
24            openableBoxes.pop();
25
26            // Go through the keys obtained from the current box and try to open corresponding boxes.
27            for (int key : keys[currentBoxId]) {
28                statuses[key] = 1; // The box that corresponds to the key can now be opened.
29                // If we have the box and have not yet opened it, collect candies and open it.
30                if (hasBox[key] && !openedBox[key]) {
31                    totalCandies += candies[key]; // Add candies from the box we can now open.
32                    openedBox[key] = true; // Mark the box as opened.
33                    openableBoxes.push(key); // Add it to the queue of boxes to process.
34                }
35            }
36
37            // Go through all boxes contained within the current box.
38            for (int containedBox : containedBoxes[currentBoxId]) {
39                hasBox[containedBox] = true; // We have this box.
40                // If the box is not locked and we haven't opened it yet, collect candies.
41                if (statuses[containedBox] && !openedBox[containedBox]) {
42                    totalCandies += candies[containedBox]; // Add candies from the contained box.
43                    openedBox[containedBox] = true; // Mark the box as opened.
44                    openableBoxes.push(containedBox); // Add it to the queue of boxes to process.
45                }
46            }
47        }
48
49        return totalCandies;
50    }
51};
52

1// Define the functions and variables in the global scope
2
3// This function calculates the maximum number of candies one can collect
4// from initially available boxes and any boxes we can subsequently open.
5// statuses: An array indicating if a box is locked (0) or unlocked (1)
6// candies: An array representing the number of candies in each box
7// keys: An array of arrays where each subarray contains keys found in a box
8// containedBoxes: An array of arrays where each subarray contains boxes found in a box
9// initialBoxes: An array of the boxes we start with
10function maxCandies(
11  statuses: number[],
12  candies: number[],
13  keys: number[][],
14  containedBoxes: number[][],
15  initialBoxes: number[]
16): number {
17  let totalCandies = 0; // Running total of collected candies
18  const numBoxes = statuses.length; // Total number of boxes
19  const hasBox = new Array<boolean>(numBoxes).fill(false); // Tracks possession of boxes
20  const openedBox = new Array<boolean>(numBoxes).fill(false); // Tracks whether a box is opened
21  const openableBoxes: number[] = []; // Queue of boxes that can be opened
22
23  // Initialize the process with the initially available boxes
24  for (const boxId of initialBoxes) {
25    hasBox[boxId] = true; // We have this box
26    if (statuses[boxId] === 1) { // If the box is unlocked
27      totalCandies += candies[boxId]; // Add its candies to the total
28      openedBox[boxId] = true; // Mark the box as opened
29      openableBoxes.push(boxId); // Add to the queue for processing
30    }
31  }
32
33  // While there are boxes that can be opened, continue processing
34  while (openableBoxes.length > 0) {
35    const currentBoxId = <number>openableBoxes.shift(); // Get the next box to process
36
37    // Process keys from the current box
38    for (const key of keys[currentBoxId]) {
39      statuses[key] = 1; // The corresponding box can now be opened (unlocked)
40      if (hasBox[key] && !openedBox[key]) { // If we have and haven't opened this box
41        totalCandies += candies[key]; // Collect its candies
42        openedBox[key] = true; // Mark it as opened
43        openableBoxes.push(key); // Add to queue for processing
44      }
45    }
46
47    // Process all boxes contained within the current box
48    for (const containedBox of containedBoxes[currentBoxId]) {
49      hasBox[containedBox] = true; // We now have this box
50      if (statuses[containedBox] === 1 && !openedBox[containedBox]) { // If it's unlocked and not opened
51        totalCandies += candies[containedBox]; // Collect its candies
52        openedBox[containedBox] = true; // Mark it as opened
53        openableBoxes.push(containedBox); // Add to queue for processing
54      }
55    }
56  }
57
58  return totalCandies; // Return the total candies collected
59}
60
61// Example usage of the function
62// const maxCollectedCandies = maxCandies([status array], [candies array], [keys array], [containedBoxes array], [initialBoxes array]);
63

Not Sure What to Study? Take the 2-min Quiz：

Which of the following problems can be solved with backtracking (select multiple)

Generating subsetsGenerating random numbersGenerating permutationsSorting integers

Time and Space Complexity

The time complexity of the given code is O(N + K + B) where N is the number of boxes, K is the total number of keys, and B is the total number of boxes inside the other boxes. This complexity arises because each box, key, and inner box is processed at most once. You process a box only when you have the key and it's available to you, which happens once for each box that meets these conditions. Similarly, you access each key and inner box only once.

The space complexity of the code is O(N). This complexity comes from storing the states (status), the box information in has and took, and the maximum size of the queue (q) which can contain all the boxes at worst if all get unlocked concurrently. The q could be less than O(N) if the boxes are opened one by one, but in the worst case, if all the boxes are obtained and can be opened, they all could be in the queue. Hence, the has and took sets, along with the queue q, contribute to the space complexity, leading to O(N) in the worst-case scenario.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1298. Maximum Candies You Can Get from Boxes

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings