Skip to content

← leetcode

Maximum Candies You Can Get from Boxes

· Hard

LeetCode problem 1298

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:

  • you find a box but it is already open
  • you find a box but you already have one or more keys for it
  • you find the key to a box that you already possess

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: O(n + k) where n is the number of boxes and k is the number of keys present
  • Space: O(n)

time taken

  • 17 minutes and 32 seconds
    • this question is really straightforward; reading it is a pain up my back-side