1298: Maximum-Candies-You-Can-Get-from-Boxes
Hard

table of contents

The hardest part of this problem was actually understanding what they wanted you to solve. Implementation wise, I would rate this as a low-medium.

It is basically just a breadth-first search implementation, where you only add to the queue if an un-opened box becomes openable. This only occurs when:

Then, we simply just find the totalCandy by summing the candy present in all these opened boxes, and return it.

code

class Solution {
public:
    int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
        vector<int> boxStatus (status.size(), 0);
        queue<int> openableBoxes;

        for (int& i : initialBoxes) {
            boxStatus[i] = 1;
            if (status[i] == 1) {
                openableBoxes.push(i);
            }
        }

        int totalCandy = 0;
        while(!openableBoxes.empty()) {
            int box = openableBoxes.front();
            openableBoxes.pop();

            totalCandy += candies[box];
            for (int& i : keys[box]) {
                ++status[i];
                if (status[i] == 1 && boxStatus[i] >= 1) {
                    openableBoxes.push(i);
                }
            }

            for (int& i : containedBoxes[box]) {
                ++boxStatus[i];
                if (boxStatus[i] == 1 && status[i] >= 1) {
                    openableBoxes.push(i);
                }
            }
        }

        return totalCandy;
    }
};

complexity

time taken