[Leetcode] 1298. Maximum Candies You Can Get from Boxes

initial

an extremly starightforwad BUT extremely hard to impl q

my init approach was wrong in
1) adding keys to queue incorrectly. Once I found key==1, I immeidiately added that box to my queue and marked that box as visited even though i might not have that box currently

2) so i didnt have a DS that keeps track of currently owned boxes so I couldnt impl 1 properly

3) i was marking the boxes as visited when i got the keys, not as i was processing them in my queue

class Solution:
    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
        queue=[]
        n= len(status)
        ans =0
        # for i in range(n):
        #     if status[i]==1 and not keys[i]:
        #         queue.append(i)
        queue = initialBoxes
        visited=set()
        while queue:
            node = queue.pop(0)
            ans+=candies[node]
            visited.add(node)
            for key in keys[node]:
                status[key]=1
                if key not in visited:
                    queue.append(key)
                    visited.add(key)
            for neigh in containedBoxes[node]:
                if status[neigh]==1 and neigh not in visited:
                    queue.append(neigh)
                    visited.add(neigh)
        return ans

sol

so i need to keep track of currently owned boxes for this logic, which i will use set and init as the initialBoxes.

class Solution:
    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
        queue=[]
        n= len(status)
        ans =0
        hasBox=set(initialBoxes)
        for box in initialBoxes:
            if status[box]:
                queue.append(box)
        visited=set()
        while queue:
            node = queue.pop(0)
            if node in visited:
                continue
            ans+=candies[node]
            visited.add(node)
            for key in keys[node]:
                status[key]=1
                if key in hasBox and key not in visited:
                    queue.append(key)
            for neigh in containedBoxes[node]:
                hasBox.add(neigh)
                if status[neigh]==1 and neigh not in visited:
                    queue.append(neigh)
        return ans

complexity

Time Complexity: O(n + E)

n = number of boxes
E = total number of edges (keys + containedBoxes relationships)

Breakdown:

Each box is processed at most once (due to visited set)
For each box processed, we iterate through its keys and contained boxes
Total iterations = sum of all keys[i] + sum of all containedBoxes[i] = E
Queue operations are O(1) amortized
Set operations (add, lookup) are O(1) average case

Space Complexity: O(n)
Breakdown:

queue: O(n) in worst case (all boxes queued)
visited: O(n) (tracks all boxes)
hasBox: O(n) (tracks all boxes)
status, candies, keys, containedBoxes: Given as input (not counted)

Why it's efficient:
This is essentially a graph traversal (BFS) where:

Nodes = boxes
Edges = keys and containedBoxes relationships
We visit each node once and traverse each edge once

The algorithm is optimal because:

No redundant work: Each box processed exactly once
Efficient tracking: Hash sets for O(1) lookups
Breadth-first exploration: Ensures we find all reachable boxes