Maximum Candies You Can Get from Boxes — LeetCode 1298 Python Solution
HardBreadth-First SearchGraphArray
- Problem
- #1298
- Pattern
- Breadth-First Search
- Reading time
- 7 min
- Source
- leetcode.com
The problem
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 ith box is open and 0 if the ith box is closed, candies[i] is the number of candies in the ith box, keys[i] is a list of the labels of the boxes you can open after opening the ith box.
Example
- 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.
Python solution
Python
class Solution:
def maxCandies(
self,
status: List[int],
candies: List[int],
keys: List[List[int]],
containedBoxes: List[List[int]],
initialBoxes: List[int],
) -> int:
q = deque()
has, took = set(initialBoxes), set()
ans = 0
for box in initialBoxes:
if status[box]:
q.append(box)
took.add(box)
ans += candies[box]
while q:
box = q.popleft()
for k in keys[box]:
if not status[k]:
status[k] = 1
if k in has and k not in took:
q.append(k)
took.add(k)
ans += candies[k]
for b in containedBoxes[box]:
has.add(b)
if status[b] and b not in took:
q.append(b)
took.add(b)
ans += candies[b]
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n), where n is the total number of boxes auxiliary |
Pattern: Breadth-First Search
Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 1298. Maximum Candies You Can Get from Boxes is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.
The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1298. Maximum Candies You Can Get from Boxes?
- LeetCode 1298. Maximum Candies You Can Get from Boxes is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1298. Maximum Candies You Can Get from Boxes?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1298. Maximum Candies You Can Get from Boxes?
- The Python solution on this page uses O(n), where n is the total number of boxes auxiliary space.
- What topics does LeetCode 1298. Maximum Candies You Can Get from Boxes cover?
- LeetCode 1298. Maximum Candies You Can Get from Boxes is tagged Breadth-First Search, Graph and Array on LeetCode.