Problem statement

https://leetcode.com/problems/maximum-candies-you-can-get-from-boxes/

Solution

I do not really like this problem: you need some time to digest all these inputs. Let boxes be set of boxes we can reach so far and queue is queue of boxes we can open so far. Each time we extract box from the left of our queue, add candies to answer. Then we add all boxes inside given box to our set of open boxes and then if this box is opened, we add it to our queue. Also we need to deal with keys: if box was closed and we alreade have access to it, we add it to queue. Also we change state of box j to open (it can happen that it was already open, but it does not matter). In the end we just return ans

Complexity

Time complexity is O(m), where m is total number of keys and boxes we have. Space complexity is O(n).

Code

class Solution:
    def maxCandies(self, status, candies, keys, containedBoxes, initialBoxes):
        boxes = set(initialBoxes) #boxes we can see
        queue = deque([i for i in boxes if status[i]]) #boxes we can open
        ans = 0

        while queue:
            i = queue.popleft()
            ans += candies[i]

            for j in containedBoxes[i]:
                boxes.add(j)
                if status[j]: 
                    queue.append(j)
                    
            for j in keys[i]:
                if status[j] == 0 and j in boxes:
                    queue.append(j)
                status[j] = 1
        
        return ans