Skip to main content
Talentd

Can You Eat Your Favorite Candy on Your Favorite Day? - Solution & Explanation

MediumArrayPrefix Sum12 min readAsked at: Fleetx
Practice this problem

Problem Statement

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:

  • You start eating candies on day 0.
  • You cannot eat any candy of type i unless you have eaten all candies of type i - 1.
  • You must eat at least one candy per day until you have eaten all the candies.

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 <= 105
  • 1 <= candiesCount[i] <= 105
  • 1 <= queries.length <= 105
  • queries[i].length == 3
  • 0 <= favoriteTypei < candiesCount.length
  • 0 <= favoriteDayi <= 109
  • 1 <= dailyCapi <= 109

Approach Overview

Problem 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.

Approach 1: Prefix Sum Calculation

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Direct Simulation

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m) where n is the number of candy types and m is the number of queries. Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct SimulationO(n * q)O(1)Small input sizes or when prefix preprocessing is unnecessary
Prefix Sum CalculationO(n + q)O(n)Best for many queries requiring fast cumulative range checks

Video Solution

LeetCode 1744. Can You Eat Your Favorite Candy on Your Favorite Day? • Happy Coding • 705 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Can You Eat Your Favorite Candy on Your Favorite Day? easy or hard?
The problem is rated Medium because the core logic requires recognizing interval overlap and applying prefix sums to handle multiple queries efficiently. Once the cumulative totals are built, the remaining work is straightforward arithmetic and comparison.
Can You Eat Your Favorite Candy on Your Favorite Day? Python/Java solution
Python and Java implementations typically build a prefix sum array first, then iterate through queries and check interval overlap conditions. The logic remains identical across languages: compute cumulative totals, determine min and max candies eaten by the day, and compare with the candy type range.
How to solve Can You Eat Your Favorite Candy on Your Favorite Day? in O(n)?
Build a prefix sum array storing cumulative candy counts up to each type. For a query, compute the minimum candies eaten by that day (favoriteDay + 1) and the maximum possible ((favoriteDay + 1) * dailyCap). If this interval overlaps with the candy range belonging to the target type, the answer is true. Each query becomes an O(1) interval comparison.
What is the best approach for Can You Eat Your Favorite Candy on Your Favorite Day??
The most efficient approach uses a prefix sum array combined with range intersection checks. Precompute cumulative candy counts for each type, then for each query compare the possible number of candies eaten by that day with the index range of the desired candy type. This reduces each query to O(1) time after O(n) preprocessing.
Is Can You Eat Your Favorite Candy on Your Favorite Day? asked at Google/Amazon/Meta?
Range reasoning and prefix sum problems similar to this appear frequently in interviews at companies like Amazon, Google, and Meta. Interviewers often expect candidates to recognize cumulative sums and convert repeated summation into constant-time queries.
What data structure is used in Can You Eat Your Favorite Candy on Your Favorite Day??
The key data structure is a prefix sum array. It stores cumulative candy counts so the total candies before any type can be retrieved instantly, enabling efficient range calculations for each query.
What is the time complexity of Can You Eat Your Favorite Candy on Your Favorite Day??
The optimal prefix sum solution runs in O(n + q) time where n is the number of candy types and q is the number of queries. Building the prefix array takes O(n), and each query is answered in constant time. Space complexity is O(n) for storing cumulative totals.

Ready to solve this problem?

Practice Can You Eat Your Favorite Candy on Your Favorite Day? with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays