Problem
You have n
boxes labeled from 0
to n - 1
. You are given four arrays: status
, candies
, keys
, and containedBoxes
where:
status[i]
is1
if theith
box is open and0
if theith
box is closed,candies[i]
is the number of candies in theith
box,keys[i]
is a list of the labels of the boxes you can open after opening theith
box.containedBoxes[i]
is a list of the boxes you found inside theith
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.
Examples
Example 1:
|
|
Example 2:
|
|
Constraints:
n == status.length == candies.length == keys.length == containedBoxes.length
1 <= n <= 1000
status[i]
is either0
or1
.1 <= candies[i] <= 1000
0 <= keys[i].length <= n
0 <= keys[i][j] < n
- All values of
keys[i]
are unique. 0 <= containedBoxes[i].length <= n
0 <= containedBoxes[i][j] < n
- All values of
containedBoxes[i]
are unique. - Each box is contained in one box at most.
0 <= initialBoxes.length <= n
0 <= initialBoxes[i] < n
Solution
Method 1 – BFS with State Tracking
Intuition
The problem is about collecting candies by opening boxes, where some boxes are locked and can only be opened if you have their keys. The process is similar to traversing a graph where boxes are nodes, and you can only visit (open) a node if you have its key or it’s already open. Using BFS ensures we process boxes as soon as they’re available, and we keep track of keys and boxes we find along the way.
Approach
- Initialization:
- Use a queue to process boxes you can open.
- Use sets to track boxes you have, keys you have, and boxes already opened.
- Processing:
- For each box in the queue:
- If it’s already opened, skip.
- If it’s closed and you don’t have the key, skip for now.
- If it’s open or you have the key:
- Collect candies.
- Mark as opened.
- Add any new keys found to your key set.
- Add any new boxes found to your box set and queue.
- If you now have keys for boxes you couldn’t open before, try them again.
- Repeat until no more boxes can be opened.
- Return the total candies collected.
Code
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(N + total_keys + total_containedBoxes)
— Each box, key, and contained box is processed at most once. - 🧺 Space complexity:
O(N)
— For tracking box states, keys, and queue.