Leetcode 1744. Can You Eat Your Favorite Candy on Your Favorite Day?

Problem Explanation

In this problem, we are given an array, candiesCount, representing the count of different types of candies, and a 2D array, queries, which consists of our favorite candy type, day, and daily limit of candies we can eat. We need to find out if it's possible to eat our favorite candy on our favorite day without eating more than daily limit. The candies have conditions: we start eating candies on day 0, and we cannot eat candy of type i unless we have eaten all candies of type i-1.

Our task is to create a boolean array answer with the same length as queries such that for each query, if we can eat our favorite candy on our favorite day without exceeding the daily limit, the corresponding element in the answer array is true, and false otherwise.

For example,

1candiesCount = [7, 4, 5, 3, 8]
2queries = [[0, 2, 2], [4, 2, 4], [2, 13, 1000000000]]
3Output: [true, false, true]

Solution Approach

To solve this problem, we can use the prefix sum technique. We calculate the prefix sum of the candiesCount array and save it in a separate array prefix. In this way, prefix[i] will represent the total candies from type 0 to type i-1 (1-indexed array).

For each query, we calculate the minimum and maximum days required to eat candies of the favorite candy type. We check if the favorite day lies between minimum and maximum days, then it is possible to eat the candy on that day without exceeding the daily limit.

Example Walkthrough

Let's go through an example:

1candiesCount = [7, 4, 5, 3, 8]
2queries = [[0, 2, 2], [4, 2, 4], [2, 13, 1000000000]]

First, compute the prefix sum array prefix of candiesCount.

1prefix = [0, 7, 11, 16, 19, 27]

Now, iterate through each query:

1. Query = [0, 2, 2] (type = 0, day = 2, cap = 2)
   • minDay = prefix[0] / 2 = 0
   • maxDay = prefix[1] - 1 = 6
   • As 2 lies between 0 and 6, the answer is True.
2. Query = [4, 2, 4] (type = 4, day = 2, cap = 4)
   • minDay = prefix[4] / 4 = 4
   • maxDay = prefix[5] - 1 = 26
   • As 2 does not lie between 4 and 26, the answer is False.
3. Query = [2, 13, 1000000000] (type = 2, day = 13, cap = 1000000000)
   • minDay = prefix[2] / 1000000000 = 0
   • maxDay = prefix[3] - 1 = 15
   • As 13 lies between 0 and 15, the answer is True.

Final answer: [True, False, True]

C++ Solution

1#include <vector>
2
3class Solution {
4 public:
5  std::vector<bool> canEat(std::vector<int>& candiesCount, std::vector<std::vector<int>>& queries) {
6    const int n = candiesCount.size();
7    std::vector<bool> ans;
8    std::vector<long> prefix{0};
9
10    // Calculate the prefix sum of candiesCount
11    for (int i = 0; i < n; ++i)
12      prefix.push_back(prefix.back() + candiesCount[i]);
13
14    for (const std::vector<int>& query : queries) {
15      const int type = query[0];
16      const int day = query[1];
17      const int cap = query[2];
18      // Compute the min/max day required to eat candy of favorite type
19      const long minDay = prefix[type] / cap;
20      const long maxDay = prefix[type + 1] - 1;
21      // Check if favorite day lies between minDay and maxDay
22      ans.push_back(minDay <= day && day <= maxDay);
23    }
24
25    return ans;
26  }
27};
28```## Python Solution
29
30```python
31from typing import List
32
33class Solution:
34    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:
35        n = len(candiesCount)
36        ans = []
37        prefix = [0]
38        
39        # Calculate the prefix sum of candiesCount
40        for i in range(n):
41            prefix.append(prefix[-1] + candiesCount[i])
42
43        for query in queries:
44            type_ = query[0]
45            day = query[1]
46            cap = query[2]
47            # Compute the min/max day required to eat candy of favorite type
48            minDay = prefix[type_] // cap
49            maxDay = prefix[type_ + 1] - 1
50            # Check if favorite day lies between minDay and maxDay
51            ans.append(minDay <= day <= maxDay)
52
53        return ans

JavaScript Solution

1var canEat = function(candiesCount, queries) {
2    const n = candiesCount.length;
3    const ans = [];
4    const prefix = [0];
5
6    // Calculate the prefix sum of candiesCount
7    for (let i = 0; i < n; ++i)
8        prefix.push(prefix[prefix.length - 1] + candiesCount[i]);
9
10    for (const query of queries) {
11        const type = query[0];
12        const day = query[1];
13        const cap = query[2];
14        // Compute the min/max day required to eat candy of favorite type
15        const minDay = Math.floor(prefix[type] / cap);
16        const maxDay = prefix[type + 1] - 1;
17        // Check if favorite day lies between minDay and maxDay
18        ans.push(minDay <= day && day <= maxDay);
19    }
20
21    return ans;
22};

Java Solution

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    public List<Boolean> canEat(int[] candiesCount, int[][] queries) {
7        int n = candiesCount.length;
8        List<Boolean> ans = new ArrayList<>();
9        long[] prefix = new long[n + 1];
10        
11        // Calculate the prefix sum of candiesCount
12        for (int i = 0; i < n; ++i)
13            prefix[i + 1] = prefix[i] + candiesCount[i];
14
15        for (int[] query : queries) {
16            int type = query[0];
17            int day = query[1];
18            int cap = query[2];
19            // Compute the min/max day required to eat candy of favorite type
20            long minDay = prefix[type] / cap;
21            long maxDay = prefix[type + 1] - 1;
22            // Check if favorite day lies between minDay and maxDay
23            ans.add(minDay <= day && day <= maxDay);
24        }
25
26        return ans;
27    }
28}