Skip to content

1298. Maximum Candies You Can Get from Boxes

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
 public:
  int maxCandies(vector<int>& status, vector<int>& candies,
                 vector<vector<int>>& keys, vector<vector<int>>& containedBoxes,
                 vector<int>& initialBoxes) {
    int ans = 0;
    queue<int> q;
    vector<bool> reachedClosedBoxes(status.size());

    auto pushBoxesIfPossible = [&status, &q,
                                &reachedClosedBoxes](const vector<int>& boxes) {
      for (const int box : boxes)
        if (status[box])
          q.push(box);
        else
          reachedClosedBoxes[box] = true;
    };

    pushBoxesIfPossible(initialBoxes);

    while (!q.empty()) {
      const int currBox = q.front();
      q.pop();

      // Add the candies.
      ans += candies[currBox];

      // Push `reachedClosedBoxes` by `key` obtained in this turn and change
      // their statuses.
      for (const int key : keys[currBox]) {
        if (!status[key] && reachedClosedBoxes[key])
          q.push(key);
        status[key] = 1;  // boxes[key] is now open.
      }

      // Push the boxes contained in `currBox`.
      pushBoxesIfPossible(containedBoxes[currBox]);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
  public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes,
                        int[] initialBoxes) {
    int ans = 0;
    Queue<Integer> q = new ArrayDeque<>();
    boolean[] reachedClosedBoxes = new boolean[status.length];

    pushBoxesIfPossible(initialBoxes, status, q, reachedClosedBoxes);

    while (!q.isEmpty()) {
      final int currBox = q.poll();

      // Add the candies.
      ans += candies[currBox];

      // Push `reachedClosedBoxes` by `key` obtained in this turn and change
      // their statuses.
      for (final int key : keys[currBox]) {
        if (status[key] == 0 && reachedClosedBoxes[key])
          q.offer(key);
        status[key] = 1; // boxes[key] is now open.
      }

      // Push the boxes contained in `currBox`.
      pushBoxesIfPossible(containedBoxes[currBox], status, q, reachedClosedBoxes);
    }

    return ans;
  }

  private void pushBoxesIfPossible(int[] boxes, int[] status, Queue<Integer> q,
                                   boolean[] reachedClosedBoxes) {
    for (final int box : boxes)
      if (status[box] == 1)
        q.offer(box);
      else
        reachedClosedBoxes[box] = true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
  def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
    ans = 0
    q = collections.deque()
    reachedClosedBoxes = [0] * len(status)

    def pushBoxesIfPossible(boxes: List[int]) -> None:
      for box in boxes:
        if status[box]:
          q.append(box)
        else:
          reachedClosedBoxes[box] = True

    pushBoxesIfPossible(initialBoxes)

    while q:
      currBox = q.popleft()

      # Add the candies.
      ans += candies[currBox]

      # Push `reachedClosedBoxes` by `key` obtained in this turn and change
      # their statuses.
      for key in keys[currBox]:
        if not status[key] and reachedClosedBoxes[key]:
          q.append(key)
        status[key] = 1  # boxes[key] is now open

      # Push the boxes contained in `currBox`.
      pushBoxesIfPossible(containedBoxes[currBox])

    return ans