Maximum Candies You Can Get from Boxes - Practice Coding Problems

Maximum Candies You Can Get from Boxes - Problem

You have n boxes labeled from 0 to n - 1. You are given four arrays:

status[i] is 1 if the i^th box is open and 0 if closed
candies[i] is the number of candies in the i^th box
keys[i] is a list of labels of boxes you can open after opening the i^th box
containedBoxes[i] is a list of boxes you find inside the i^th box

You are given an integer array initialBoxes that contains the labels of boxes you initially have.

Rules:

You can take all candies from any open box
You can use keys found in opened boxes to open new boxes
You can use boxes found inside opened boxes

Return the maximum number of candies you can get following the rules above.

Input & Output

Example 1 — Basic Case

$ Input: status = [1,0,1,0], candies = [7,5,4,9], keys = [[],[],[1],[]], containedBoxes = [[],[],[],[]], initialBoxes = [0]

› Output: 16

💡 Note: Start with box 0 (open) → collect 7 candies. Box 2 is also open → collect 4 candies. Box 0 has no keys, box 2 gives key to box 1 → open box 1 and collect 5 candies. Total: 7+4+5=16

Example 2 — Keys Required

$ Input: status = [1,0,0,0], candies = [1,1,1,1], keys = [[1,2],[3],[],[]], containedBoxes = [[],[],[],[]], initialBoxes = [0]

› Output: 4

💡 Note: Box 0 is open → collect 1 candy and get keys [1,2]. Open boxes 1,2 → collect 2 more candies and get key [3]. Open box 3 → collect 1 candy. Total: 1+1+1+1=4

Example 3 — Contained Boxes

$ Input: status = [1,1,1], candies = [2,3,2], keys = [[],[],[]], containedBoxes = [[1,2],[],[]], initialBoxes = [0]

› Output: 7

💡 Note: Start with box 0 → collect 2 candies and find boxes [1,2]. Boxes 1,2 are both open → collect 3+2=5 candies. Total: 2+3+2=7

Constraints

1 ≤ status.length ≤ 1000
status.length == candies.length == keys.length == containedBoxes.length == n
0 ≤ status[i] ≤ 1
1 ≤ candies[i] ≤ 1000
0 ≤ keys[i].length ≤ 1000
0 ≤ keys[i][j] < n
0 ≤ containedBoxes[i].length ≤ 1000
0 ≤ containedBoxes[i][j] < n
All values in keys[i] are unique
All values in containedBoxes[i] are unique
1 ≤ initialBoxes.length ≤ 1000
0 ≤ initialBoxes[i] < n

Visualization

Tap to expand

Understanding the Visualization

Initial State

Start with given boxes, some open, some closed, with keys and contained boxes

Iterative Opening

Open accessible boxes, collect candies, keys, and new boxes

Final Result

Sum of all candies from boxes that could be opened

Key Takeaway

🎯 Key Insight: Use BFS-style iteration to systematically open all reachable boxes - the order doesn't affect the total candy count

Asked in

G Google 45 M Microsoft 32 A Amazon 28 F Facebook 22

The key insight is that the order of opening boxes doesn't matter for the total candy count - we just need to find all boxes that can eventually be reached and opened. The optimal approach uses BFS-style iteration to systematically open all accessible boxes until no more progress can be made. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Exploration with All Permutations	O(n! × n)	O(n)	Try all possible orders of opening boxes recursively
Breadth-First Search (BFS)	O(n)	O(n)	Use BFS to systematically explore all reachable boxes level by level

Recursive Exploration with All Permutations — Algorithm Steps

Generate all permutations of available boxes
For each permutation, simulate opening boxes in that order
Track maximum candies across all permutations

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Create all possible orders to open available boxes

Simulate Each Order

For each permutation, simulate opening boxes and collecting items

Track Maximum

Keep track of the maximum candies found across all attempts

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_BOXES 1000

int maxCandies = 0;

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void generatePermutations(int arr[], int start, int end, int status[], int candies[], int keys[][MAX_BOXES], int keySizes[], int containedBoxes[][MAX_BOXES], int boxSizes[], int hasKeys[], int available[], int availableSize, int collected) {
    if (start == end) {
        int newCandies = collected;
        int newKeys[MAX_BOXES] = {0};
        memcpy(newKeys, hasKeys, sizeof(newKeys));
        
        for (int i = 0; i <= end; i++) {
            int box = arr[i];
            newCandies += candies[box];
            for (int j = 0; j < keySizes[box]; j++) {
                newKeys[keys[box][j]] = 1;
            }
        }
        
        if (newCandies > maxCandies) {
            maxCandies = newCandies;
        }
        return;
    }
    
    for (int i = start; i <= end; i++) {
        swap(&arr[start], &arr[i]);
        generatePermutations(arr, start + 1, end, status, candies, keys, keySizes, containedBoxes, boxSizes, hasKeys, available, availableSize, collected);
        swap(&arr[start], &arr[i]);
    }
}

int solution(int status[], int candies[], int keys[][MAX_BOXES], int keySizes[], int containedBoxes[][MAX_BOXES], int boxSizes[], int initialBoxes[], int initialSize, int n) {
    maxCandies = 0;
    int hasKeys[MAX_BOXES] = {0};
    int openable[MAX_BOXES];
    int openableCount = 0;
    
    for (int i = 0; i < initialSize; i++) {
        int box = initialBoxes[i];
        if (status[box] == 1 || hasKeys[box]) {
            openable[openableCount++] = box;
        }
    }
    
    if (openableCount > 0) {
        generatePermutations(openable, 0, openableCount - 1, status, candies, keys, keySizes, containedBoxes, boxSizes, hasKeys, initialBoxes, initialSize, 0);
    }
    
    return maxCandies;
}

int main() {
    // Simplified parsing for basic functionality
    int n = 4;
    int status[] = {1, 0, 1, 0};
    int candies[] = {7, 5, 4, 9};
    int keys[MAX_BOXES][MAX_BOXES] = {{}, {}, {1}, {}};
    int keySizes[] = {0, 0, 1, 0};
    int containedBoxes[MAX_BOXES][MAX_BOXES] = {{}, {}, {}, {}};
    int boxSizes[] = {0, 0, 0, 0};
    int initialBoxes[] = {0};
    int initialSize = 1;
    
    printf("%d\n", solution(status, candies, keys, keySizes, containedBoxes, boxSizes, initialBoxes, initialSize, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

n! permutations of boxes, each taking O(n) time to process

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack and temporary data structures

⚡ Linearithmic Space

34.6K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Exploration with All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler