We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Candies You Can Get from Boxes

Difficulty: Hard

Problem Description

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.

Key Insights

  • You can only collect candies from open boxes.
  • Opening a box may yield new keys to other boxes and additional boxes to open.
  • The problem can be approached using a graph traversal technique, specifically Breadth-First Search (BFS).
  • The state of each box (open/closed) and the contents (candies, keys, contained boxes) must be carefully managed.

Space and Time Complexity

Time Complexity: O(n), where n is the number of boxes, as we may need to visit each box at least once.

Space Complexity: O(n), for storing the keys and the boxes to be opened.

Solution

We can solve the problem using a Breadth-First Search (BFS) approach. The key data structures used are:

  1. A queue to manage the boxes that need to be processed.
  2. Sets to track which boxes are currently open and which keys have been collected.

The algorithm proceeds as follows:

  1. Initialize a queue with the initial boxes.
  2. For each box processed, collect candies if the box is open.
  3. Add keys to a set for boxes that can be opened later.
  4. Add newly found boxes to a list for future processing.
  5. Continue until there are no more boxes to process.

This approach ensures that we efficiently explore all available boxes and maximize the candies collected.

Code Solutions

from collections import deque

def maxCandies(status, candies, keys, containedBoxes, initialBoxes):
    total_candies = 0
    open_boxes = set()
    keys_set = set()
    queue = deque(initialBoxes)

    # Add initially open boxes to the set
    for i in range(len(status)):
        if status[i] == 1:
            open_boxes.add(i)

    while queue:
        box = queue.popleft()
        # If the box is open, collect candies
        if box in open_boxes:
            total_candies += candies[box]
            # Collect keys from this box
            for key in keys[box]:
                keys_set.add(key)
            # Collect boxes from this box
            for new_box in containedBoxes[box]:
                if new_box not in open_boxes and new_box not in queue:
                    queue.append(new_box)

        # If the box is closed, check if we have the key
        if box not in open_boxes and box in keys_set:
            open_boxes.add(box)

        # Process keys and open new boxes if possible
        while keys_set:
            key = keys_set.pop()
            if status[key] == 1 and key not in open_boxes:
                open_boxes.add(key)
                queue.append(key)

    return total_candies
← Back to All Questions