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.
Flowchart Walkthrough
Let's analyze the problem using the algorithm flowchart to determine the appropriate algorithm. We will step through the flowchart logically to figure out if Breadth-First Search (BFS) is the suitable method for solving Leetcode 1298. Maximum Candies You Can Get from Boxes. Here's how we can use the flowchart:
-
Is it a graph?
- Yes: Although not immediately obvious as a traditional graph problem, the boxes in the problem can be represented as nodes. Each node (box) potentially has links (keys) to other nodes (boxes), forming a graph-like structure.
-
Is it a tree?
- No: The relationships between boxes can form cycles because you can get keys from one box to open another and potentially get a new key for a previously opened box. This cycle denies a tree structure.
-
Is the problem related to directed acyclic graphs (DAGs)?
- No: As established, the presence of potential cycles negates the DAG nature.
-
Is the problem related to shortest paths?
- No: We are maximizing candies collected from the boxes, not looking for shortest path or minimum spans.
-
Does the problem involve connectivity?
- Yes: The problem involves figuring out which boxes you can open dependent on the other boxesā contents (like keys obtained from other boxes). Checking the reach or connectivity between boxes based on the given keys and initial open states is crucial.
-
Does the problem have small constraints?
- According to the problem data, the constraints are mode, preferring an approach that handles a broader range, rather than optimizing for small-specific case.
- No: This pushes the flowchart towards considering BFS or DFS because BFS can explore each layer of connectivity effectively.
Given the nature of the problem where opening one box can allow access to others and we need to explore this iteratively as we collect more keys, BFS is the optimal choice. BFS lets us handle the scenario level-by-level, or in this case, box-by-box as keys are acquired, ensuring we review all accessible boxes in an orderly manner.
In conclusion, following the flowchart and considering the nuances of this specific problem, BFS is the suggested method to solve Leetcode 1298. Maximum Candies You Can Get from Boxes, as we need effective management of expanding opportunities (box openings
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.
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) calledq
to hold the indexes of all open boxes we initially have (status[i] == 1
) frominitialBoxes
. -
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 calledtook
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 asq
is not empty. For each box indexi
:a. Iterate over the list of keys in
keys[i]
, and for each keyk
: - Set the status of the box with the labelk
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 toans
, mark it astook
, and append the box index to queueq
to process its contents.b. Iterate over the list of boxes in
containedBoxes[i]
, and for each contained boxj
: - Add boxj
to the sethas
(now we have this box). - If the boxj
is open (status[j]
) and we haven't taken candies from it (j not in took
), add the number of candies from that box toans
, mark it astook
, and append the box index to queueq
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 frominitialBoxes
, which are box 0 and box 1. But since box 1 is closed, we only add box 0 toq
: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 andtook = {0}
because we've taken candies from box 0. -
We begin the BFS loop:
-
Dequeuing box 0 from
q
, no keys inkeys[0]
but we have a contained boxcontainedBoxes[0] = [2]
. We add box 2 tohas
, since it's open, add its candies toans
(total now 10), and mark it astook
. Now,q = deque([2])
. -
Dequeuing box 2 from
q
, we find a key inkeys[2] = [3]
that opens box 3. We add candies from box 3 (since it's now open and we have it inhas
), increasingans
to 14, and add box 3 totook
. 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
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.
In a binary min heap, the maximum element can be found in:
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we