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:
- 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.
- 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.
- 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}
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.