Maximum Candies You Can Get from Boxes

Hard

Airbnb

2 views

Topics:

GraphsArrays

You have n boxes labeled from 0 to n - 1. You are given four arrays: status, candies, keys, and containedBoxes where:

status[i] is 1 if the i^th box is open and 0 if the i^th box is closed,
candies[i] is the number of candies in the i^th box,
keys[i] is a list of the labels of the boxes you can open after opening the i^th box.
containedBoxes[i] is a list of the boxes you found inside the i^th box.

You are given an integer array initialBoxes that contains the labels of the boxes you initially have. You can take all the candies in any open box and you can use the keys in it to open new boxes and you also can use the boxes you find in it.

Return the maximum number of candies you can get following the rules above.

Example 1:

Input: status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]
Output: 16
Explanation: 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
Explanation: 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

Maximum Candies You Can Get from Boxes

Hard

Airbnb

2 views

Topics:

GraphsArrays

You have n boxes labeled from 0 to n - 1. You are given four arrays: status, candies, keys, and containedBoxes where:

status[i] is 1 if the i^th box is open and 0 if the i^th box is closed,
candies[i] is the number of candies in the i^th box,
keys[i] is a list of the labels of the boxes you can open after opening the i^th box.
containedBoxes[i] is a list of the boxes you found inside the i^th box.

You are given an integer array initialBoxes that contains the labels of the boxes you initially have. You can take all the candies in any open box and you can use the keys in it to open new boxes and you also can use the boxes you find in it.

Return the maximum number of candies you can get following the rules above.

Example 1:

Input: status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]
Output: 16
Explanation: 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
Explanation: 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

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the number of boxes (`n`), the number of candies in each box, and the number of keys in each box?
Can I assume that `initialBoxes` only contains valid indices within the range of `boxes`?
If it's impossible to open any more boxes (i.e., I'm stuck), should I return the total candies I've collected so far, or is there a specific error value I should return (e.g., -1)?
Are there any constraints on the number of keys a box can contain, or is it possible for a box to contain more keys than there are total boxes?
If I have multiple keys that can open the same box, does opening that box consume all the keys, or only one?

Brute Force Solution

Approach

The brute force approach for this problem is like trying every possible combination of opening boxes. We explore each possibility to find the maximum number of candies we can get by opening different boxes in different orders.

Here's how the algorithm would work step-by-step:

Start with the boxes you initially have keys for.
Try opening only some of these boxes and see how many candies you get.
Then try opening all of these boxes, and see how many candies you get.
For each combination of boxes you open, see if any of these boxes contain keys to other boxes you haven't yet opened.
If they do, then try all the different combinations of opening *those* boxes as well.
Keep doing this, exploring every possible path of opening boxes and finding new keys.
For each path, calculate the total number of candies you can collect.
Finally, compare all the totals, and choose the largest one. That is the maximum number of candies you can get.

Code Implementation

def max_candies_brute_force(candies, boxes, keys, contained_boxes, initial_boxes):

    def get_max_candies(current_boxes, opened_boxes):
        max_candies_collected = 0
        number_of_boxes = len(current_boxes)

        # Consider all possible combinations of opening the current boxes
        for i in range(1 << number_of_boxes):
            total_candies = 0
            new_keys = set()
            new_boxes = set()
            current_opened_boxes = set(opened_boxes)

            # Iterate through the boxes and check if we open them in this combination
            for j in range(number_of_boxes):
                if (i >> j) & 1:
                    box_index = current_boxes[j]

                    # Ensure not opening the box again
                    if box_index not in current_opened_boxes:
                        total_candies += candies[box_index]
                        current_opened_boxes.add(box_index)

                        # Add keys from opened box
                        for key in keys[box_index]:
                            new_keys.add(key)

                        # Add boxes contained in opened box
                        for contained_box in contained_boxes[box_index]:
                            new_boxes.add(contained_box)

            # Find newly accessible boxes based on acquired keys
            accessible_boxes = []
            for box_index in new_boxes:
                if box_index not in current_opened_boxes and box_index in new_keys or box_index in initial_boxes:
                    accessible_boxes.append(box_index)

            # Explore further if we found new boxes
            if accessible_boxes:
                total_candies += get_max_candies(accessible_boxes, current_opened_boxes)

            max_candies_collected = max(max_candies_collected, total_candies)

        return max_candies_collected

    # Start recursion with initial boxes
    max_candies = get_max_candies(initial_boxes, set())

    return max_candies

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The provided brute force approach explores all possible combinations of opening boxes. In the worst-case scenario, we have n boxes and for each box, we either choose to open it or not, resulting in 2^n possible combinations. For each of these combinations, we may need to iterate through the opened boxes to collect candies and find new keys, which takes O(n) time in the worst case. Therefore, the overall time complexity is O(n * 2^n). However, since 2^n dominates n, we can approximate the complexity as O(2^n).

Space Complexity

O(2^N) – The brute force approach explores every possible combination of opening boxes. This exploration can be visualized as a binary tree where each node represents a decision to open or not open a box. In the worst-case scenario, with N boxes, we might need to store up to 2^N combinations as we recursively explore each branch of the tree, representing the combinations of boxes opened and not opened. Furthermore, each function call in the recursive tree will require stack space. Therefore, the recursion stack can grow to a depth of N, but more significantly, the number of paths to explore leads to a space complexity proportional to 2^N, dominating the stack space complexity. This occurs because we are considering all possible subsets of the boxes.

Optimal Solution

Approach

This problem is like exploring a maze where you want to collect the most candies. We'll use a strategy to systematically open boxes and collect candies, and we keep track of what keys we have to unlock more boxes. The core idea is to explore boxes as soon as we have the key to open them.

Here's how the algorithm would work step-by-step:

Start with the boxes you can initially open (the ones you are given at the beginning).
Open a box and collect all the candies inside.
Also, collect all the keys that were inside the box you just opened.
Now, check if you can open any new boxes with the keys you just collected.
If you can open new boxes, open them, collect candies and keys, and repeat the process.
Keep doing this until you run out of boxes you can open with the keys you have.
The maximum number of candies you can get is the sum of all the candies you collected along the way.

Code Implementation

def maximum_candies(candies, boxes, keys, initial_boxes):
    number_of_boxes = len(candies)
    opened_boxes = [False] * number_of_boxes
    available_keys = set()
    boxes_to_open = initial_boxes[:] # Copy initial boxes to avoid modifying the input
    total_candies = 0

    while boxes_to_open:
        new_boxes_to_open = []
        for box_index in boxes_to_open:
            # If we haven't opened the box and have the key
            if not opened_boxes[box_index] and box_index in available_keys or box_index in initial_boxes:
                opened_boxes[box_index] = True
                total_candies += candies[box_index]

                # Collect the keys in the box
                for key in boxes[box_index]:
                    available_keys.add(key)

                # Add newly unlockable boxes to queue
                for new_box_index in range(number_of_boxes):
                    if new_box_index in available_keys and not opened_boxes[new_box_index]:
                        new_boxes_to_open.append(new_box_index)

        # Prevents infinite loops if no new boxes can be opened
        if not new_boxes_to_open:
            break

        boxes_to_open = new_boxes_to_open

    return total_candies

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the boxes, where n is the number of boxes. In the worst-case scenario, we might open each box once and collect its candies and keys. The while loop continues as long as we can open new boxes, but each box is opened at most once. Therefore, the overall time complexity is proportional to the number of boxes, resulting in O(n).

Space Complexity

O(N) – The algorithm maintains a queue (or list) of boxes that can be opened. In the worst-case scenario, we might have keys to open all N boxes, resulting in the queue holding at most N box indices. Additionally, we might use a boolean array of size N to keep track of opened boxes, further contributing to O(N) space. Therefore, the auxiliary space used is proportional to the number of boxes, N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty boxes array	Return 0 because there are no boxes to start with, so no candies can be obtained.
Empty keys array when boxes are available	Start with boxes[0] if initialBoxes[0] is true; otherwise, you cannot open any box and return 0.
No initial boxes open	If initialBoxes contains all false values and you have keys, the solution should open available boxes iteratively until no new boxes can be opened, or all boxes are visited.
Circular key dependencies (box A has key to box B, box B has key to box A)	Use a visited set to prevent infinite loops in the BFS/DFS; add a box to visited only if it is openable (either initially open, or key available and has not been visited).
Integer overflow in candies array	Use a data type with a larger range (e.g., long) to store the total number of candies if candies[i] can be very large, avoid overflow in calculating total candy.
Maximum number of boxes and keys	Consider using iterative approach (BFS) instead of recursive one (DFS) if the depth of boxes can become very deep in order to avoid StackOverflowError and use a boolean array to track visited boxes efficiently.
All boxes have zero candies	The algorithm should still correctly open available boxes based on the given keys, returning 0 as the total candies collected.
A box has a key that opens itself	Handle this as a normal case as the key just opens the box one more time and the visited set prevents re-opening, preventing cycles and ensuring correctness.