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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Candies You Can Get from Boxes

Number: 1424

Difficulty: Hard

Paid? No

Companies: Lyft, Airbnb

Problem Description

You are given n boxes labeled from 0 to n-1. Each box has an initial status (open or closed), a number of candies, keys which can open other boxes, and possibly contains additional boxes. You also have an initial list of boxes. The goal is to collect as many candies as possible by opening boxes (using keys when available) and using any new boxes found inside other boxes.

Key Insights

  • The problem resembles a graph traversal where boxes represent nodes and keys/contained boxes represent edges.
  • Use a BFS or iterative traversal strategy to simulate discovering and opening boxes.
  • When an open box is encountered, process its candies, keys, and contained boxes.
  • Track boxes that are pending (i.e., you've discovered them but can't open yet due to missing keys) and open them once the necessary key is obtained.
  • Avoid processing the same box multiple times.

Space and Time Complexity

Time Complexity: O(n + k + b) where n is the number of boxes, k is the total number of keys in all boxes, and b is the sum of all contained boxes. Space Complexity: O(n) for storing state, queues, and visited status.

Solution

We use a Breadth-First Search (BFS) approach to traverse the boxes. We initialize the BFS queue with the initial boxes. For every box processed:

  • If it is open, collect its candies.
  • Process keys found within the box to potentially open more boxes that were previously inaccessible.
  • Process contained boxes by adding them to the queue or storing them as pending if their status remains closed. We continue the process until no more boxes can be opened or processed.

The key challenge is handling when a closed box becomes open due to obtaining a key later. Hence, we keep track of pending boxes and update their status when their keys are found.

Code Solutions

# Python solution with line-by-line comments

from collections import deque

def maxCandies(status, candies, keys, containedBoxes, initialBoxes):
    n = len(status)
    # visited prevents processing the same box more than once
    visited = [False] * n
    # pending holds boxes that are discovered but closed until a key is acquired
    pending = set()
    # deque for BFS traversal
    queue = deque(initialBoxes)
    total_candies = 0
    
    while queue:
        box = queue.popleft()
        # Skip if already visited
        if visited[box]:
            continue
        visited[box] = True
        
        # If box is closed and we don't have a key, add to pending and continue
        if status[box] == 0:
            pending.add(box)
            continue
        
        # Collect candies from the open box
        total_candies += candies[box]
        
        # Process keys found in the box
        for key in keys[box]:
            # Open the box that the key corresponds to
            if status[key] == 0:
                status[key] = 1
                # If that box was pending, we can now add it to our BFS queue
                if key in pending:
                    queue.append(key)
                    pending.remove(key)
        # Process contained boxes found in the current box
        for contained in containedBoxes[box]:
            queue.append(contained)
            
    return total_candies

# Example usage:
if __name__ == "__main__":
    status = [1,0,1,0]
    candies = [7,5,4,100]
    keys = [[],[],[1],[]]
    containedBoxes = [[1,2],[3],[],[]]
    initialBoxes = [0]
    print(maxCandies(status, candies, keys, containedBoxes, initialBoxes))  # Output: 16
← Back to All Questions