You are given a (0-indexed) array of positive integers candiesCount where candiesCount[i] represents the number of candies of the ith type you have. You are also given a 2D array queries where queries[i] = [favoriteTypei, favoriteDayi, dailyCapi].
You play a game with the following rules:
0.i unless you have eaten all candies of type i - 1.Construct a boolean array answer such that answer.length == queries.length and answer[i] is true if you can eat a candy of type favoriteTypei on day favoriteDayi without eating more than dailyCapi candies on any day, and false otherwise. Note that you can eat different types of candy on the same day, provided that you follow rule 2.
Return the constructed array answer.
Example 1:
Input: candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]] Output: [true,false,true] Explanation: 1- If you eat 2 candies (type 0) on day 0 and 2 candies (type 0) on day 1, you will eat a candy of type 0 on day 2. 2- You can eat at most 4 candies each day. If you eat 4 candies every day, you will eat 4 candies (type 0) on day 0 and 4 candies (type 0 and type 1) on day 1. On day 2, you can only eat 4 candies (type 1 and type 2), so you cannot eat a candy of type 4 on day 2. 3- If you eat 1 candy each day, you will eat a candy of type 2 on day 13.
Example 2:
Input: candiesCount = [5,2,6,4,1], queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]] Output: [false,true,true,false,false]
Constraints:
1 <= candiesCount.length <= 1051 <= candiesCount[i] <= 1051 <= queries.length <= 105queries[i].length == 30 <= favoriteTypei < candiesCount.length0 <= favoriteDayi <= 1091 <= dailyCapi <= 109Problem Overview: You are given an array candiesCount where each index represents how many candies exist for a type. Queries ask whether you can eat a candy of a specific type on a specific day while respecting two rules: you must eat at least one candy per day and at most dailyCap candies. The goal is to determine if reaching that candy type on that day is possible.
Approach 1: Direct Simulation (Brute Force) (Time: O(n * q), Space: O(1))
Simulate the candy consumption process for each query. For a query [favoriteType, favoriteDay, dailyCap], calculate how many candies you could have eaten by that day and check if the target candy type is reachable. This may involve iterating through previous candy types to compute totals each time. The method works but becomes slow when both the number of candy types and queries grow large because repeated summation is expensive.
Approach 2: Prefix Sum Calculation (Optimal) (Time: O(n + q), Space: O(n))
Precompute a prefix sum array where prefix[i] stores the total candies from type 0 to i. For each query, compute two ranges: the minimum candies you must have eaten by that day (favoriteDay + 1) and the maximum candies you could have eaten ((favoriteDay + 1) * dailyCap). The candies of the desired type occupy the range (prefix[type-1] + 1) to prefix[type]. If these two ranges overlap, it means reaching that candy type on that day is feasible. Prefix sums eliminate repeated summation and reduce each query to constant-time range checks.
This technique relies on cumulative totals, a common pattern when solving problems involving running counts across an array. The precomputation step transforms repeated work into a single pass, which is why prefix sum methods frequently appear in interview problems with many queries.
Recommended for interviews: The prefix sum approach is the expected solution. It demonstrates understanding of cumulative preprocessing and interval reasoning. Mentioning the direct simulation method first shows baseline reasoning, but using prefix sums to answer each query in O(1) time is what interviewers typically look for.
This approach involves calculating prefix sums of the candies to find out how many candies should be eaten before a specific type. For each query, you have to check if it's feasible to reach that type on the specified day by eating within the daily cap.
This C solution uses a prefix sum array to calculate the number of candies that need to be eaten before reaching a given type. For each query, it checks if the number of candies that can be eaten on or before `favoriteDay` is enough but not exceeding those available for the `favoriteType` candy.
Time Complexity: O(n + m) where n is the number of candy types and m is the number of queries. Space Complexity: O(n) for the prefix sums.
In the direct simulation approach, each query is individually checked without any preprocessing of the candies. This is more straightforward and easier to implement but less efficient for large input sizes.
The C solution simulates eating by directly summing candies, verifying each query individually. This confirmation involves ensuring the `favoriteDay` range encapsulates the required `favoriteType` candies based on conditions.
Time Complexity: O(n * m) where n is the number of candy types and m is the number of queries. Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Prefix Sum Calculation | Time Complexity: O(n + m) where n is the number of candy types and m is the number of queries. Space Complexity: O(n) for the prefix sums. |
| Direct Simulation | Time Complexity: O(n * m) where n is the number of candy types and m is the number of queries. Space Complexity: O(1). |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation | O(n * q) | O(1) | Small input sizes or when prefix preprocessing is unnecessary |
| Prefix Sum Calculation | O(n + q) | O(n) | Best for many queries requiring fast cumulative range checks |
LeetCode 1744. Can You Eat Your Favorite Candy on Your Favorite Day? • Happy Coding • 690 views views
Watch 5 more video solutions →Practice Can You Eat Your Favorite Candy on Your Favorite Day? with our built-in code editor and test cases.
Practice on FleetCode