LeetCode 1744 - Can You Eat Your Favorite Candy on Your Favorite Day?

LeetCode Problem 1744

Difficulty: 🟡 Medium
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem gives us an array candiesCount where candiesCount[i] represents how many candies exist for candy type i. Candy types must be eaten in order, which means you cannot eat any candy of type i until every candy from all previous types 0 through i - 1 has already been eaten.

You are also given multiple queries. Each query contains:

• favoriteType
• favoriteDay
• dailyCap

For each query, we must determine whether it is possible to eat at least one candy of type favoriteType on day favoriteDay, while following all rules:

1. You start eating on day 0.
2. You must eat at least one candy every day.
3. You cannot eat more than dailyCap candies on any day.
4. Candy types must be consumed in order.

The output is a boolean array where each position corresponds to one query.

The constraints are large:

• Up to 10^5 candy types
• Up to 10^5 queries
• Day values and caps can be as large as 10^9

These constraints immediately tell us that simulating day by day is impossible. We need a mathematical or prefix-sum based solution.

An important observation is that for a given day:

• There is a minimum number of candies you must have eaten by then
• There is a maximum number of candies you could have eaten by then

We can treat each query as a range overlap problem.

Several edge cases are important:

• A query may ask about day 0
• dailyCap may be extremely large
• The favorite candy type may be the first or last type
• Prefix sums can become very large, so 64-bit integers are required
• A candy type may become unreachable because earlier candy types consume too many days

Approaches

Brute Force Approach

A brute-force solution would attempt to simulate candy consumption for every query.

For each query:

1. Simulate eating candies day by day
2. Respect the maximum daily cap
3. Track which candy type is currently available
4. Check whether the target candy type can be eaten on the target day

This approach is conceptually correct because it directly follows the rules of the problem. However, it becomes infeasible very quickly.

The value of favoriteDay can reach 10^9, which makes day-by-day simulation impossible. Even simulating greedily would still be far too slow for 10^5 queries.

Key Insight for the Optimal Solution

Instead of simulating consumption, we can reason about ranges.

Suppose we are answering a query:

• favoriteType = t
• favoriteDay = d
• dailyCap = c

By day d:

• The minimum number of candies eaten is d + 1, because you must eat at least one candy per day.
• The maximum number of candies eaten is (d + 1) * c.

Now consider candy type t.

Let:

• prefix[t] = total candies from types 0 through t
• prefix[t - 1] = total candies before type t

Then:

• The first candy of type t is candy number prefix[t - 1] + 1
• The last candy of type t is candy number prefix[t]

To eat a candy of type t on day d, the range of candies eaten by day d must overlap with the range occupied by type t.

This becomes an interval overlap problem.

The query is possible if:

maximum candies eaten by day d >= first candy of type t
AND
minimum candies eaten by day d <= last candy of type t

Or equivalently:

(d + 1) * c > prefix[t - 1]
AND
(d + 1) <= prefix[t]

This transforms the problem into efficient prefix sum lookups.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(Q × D)	O(1)	Simulates candy consumption day by day
Optimal	O(N + Q)	O(N)	Uses prefix sums and interval overlap logic

Where:

• N = len(candiesCount)
• Q = len(queries)
• D can be as large as 10^9

Algorithm Walkthrough

1. Build a prefix sum array.

The prefix sum array stores the cumulative number of candies up to each type.

prefix[i] = candiesCount[0] + candiesCount[1] + ... + candiesCount[i]

This allows us to quickly determine:

• How many candies exist before a type
• The total candies up to a type

2. Process each query independently.

For a query [favoriteType, favoriteDay, dailyCap]:

• Let:

t = favoriteType
d = favoriteDay
c = dailyCap

3. Compute the minimum candies eaten by day d.

Since at least one candy must be eaten each day:

minEaten = d + 1

4. Compute the maximum candies eaten by day d.

Since at most c candies can be eaten each day:

maxEaten = (d + 1) * c

5. Compute the candy range for type t.

The candies belonging to type t occupy:

firstCandy = prefix[t - 1] + 1
lastCandy = prefix[t]

If t == 0, then:

firstCandy = 1

6. Check whether the ranges overlap.

We can eat type t on day d if:

maxEaten >= firstCandy
AND
minEaten <= lastCandy

7. Store the boolean result.

Repeat this process for all queries.

Why it works

The algorithm works because every valid eating schedule produces a total number of candies eaten by day d that lies between:

[d + 1, (d + 1) * dailyCap]

Candy type t occupies a fixed interval in the global candy ordering:

[firstCandy, lastCandy]

If these intervals overlap, then there exists some valid number of candies eaten by day d that lands within the range for type t. Therefore, eating type t on day d is possible.

If the intervals do not overlap, then no valid eating schedule can reach type t on that day.

Python Solution

from typing import List

class Solution:
    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:
        n = len(candiesCount)

        # Build prefix sums
        prefix = [0] * n
        prefix[0] = candiesCount[0]

        for i in range(1, n):
            prefix[i] = prefix[i - 1] + candiesCount[i]

        answer = []

        for favoriteType, favoriteDay, dailyCap in queries:
            min_eaten = favoriteDay + 1
            max_eaten = (favoriteDay + 1) * dailyCap

            candies_before = prefix[favoriteType - 1] if favoriteType > 0 else 0
            candies_up_to = prefix[favoriteType]

            can_eat = (
                max_eaten > candies_before and
                min_eaten <= candies_up_to
            )

            answer.append(can_eat)

        return answer

The implementation begins by constructing a prefix sum array. This array allows constant-time lookup of how many candies exist before a specific type and how many candies exist up to that type.

For each query, the code computes:

• The minimum possible candies eaten by the target day
• The maximum possible candies eaten by the target day

It then determines the interval occupied by the favorite candy type.

The condition:

max_eaten > candies_before

ensures that we can reach the target type by that day.

The condition:

min_eaten <= candies_up_to

ensures that we have not already exhausted the target type before that day.

If both conditions hold, the intervals overlap and the answer is True.

Go Solution

func canEat(candiesCount []int, queries [][]int) []bool {
	n := len(candiesCount)

	// Build prefix sums using int64 to avoid overflow
	prefix := make([]int64, n)
	prefix[0] = int64(candiesCount[0])

	for i := 1; i < n; i++ {
		prefix[i] = prefix[i-1] + int64(candiesCount[i])
	}

	answer := make([]bool, len(queries))

	for i, query := range queries {
		favoriteType := query[0]
		favoriteDay := int64(query[1])
		dailyCap := int64(query[2])

		minEaten := favoriteDay + 1
		maxEaten := (favoriteDay + 1) * dailyCap

		var candiesBefore int64 = 0
		if favoriteType > 0 {
			candiesBefore = prefix[favoriteType-1]
		}

		candiesUpTo := prefix[favoriteType]

		canEatCandy := (
			maxEaten > candiesBefore &&
				minEaten <= candiesUpTo
		)

		answer[i] = canEatCandy
	}

	return answer
}

The Go implementation follows the same logic as the Python solution. The main difference is that Go requires explicit handling of integer overflow.

Since values can exceed 32-bit integer limits:

(10^9 + 1) * 10^9

all prefix sums and arithmetic involving days or caps use int64.

Slices are used naturally for prefix sums and results. No special handling for nil slices is necessary because the constraints guarantee valid input sizes.

Worked Examples

Example 1

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

Step 1: Build Prefix Sum

Type	Candies	Prefix Sum
0	7	7
1	4	11
2	5	16
3	3	19
4	8	27

Query 1: [0,2,2]

Variable	Value
favoriteType	0
favoriteDay	2
dailyCap	2
minEaten	3
maxEaten	6
candiesBefore	0
candiesUpTo	7

Check conditions:

6 > 0     -> true
3 <= 7    -> true

Answer: true

Query 2: [4,2,4]

Variable	Value
favoriteType	4
favoriteDay	2
dailyCap	4
minEaten	3
maxEaten	12
candiesBefore	19
candiesUpTo	27

Check conditions:

12 > 19   -> false
3 <= 27   -> true

Answer: false

We cannot reach type 4 by day 2.

Query 3: [2,13,1000000000]

Variable	Value
favoriteType	2
favoriteDay	13
dailyCap	1000000000
minEaten	14
maxEaten	14000000000
candiesBefore	11
candiesUpTo	16

Check conditions:

14000000000 > 11   -> true
14 <= 16           -> true

Answer: true

Example 2

candiesCount = [5,2,6,4,1]
queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]

Prefix Sum

Type	Candies	Prefix Sum
0	5	5
1	2	7
2	6	13
3	4	17
4	1	18

Query Analysis

Query	minEaten	maxEaten	candiesBefore	candiesUpTo	Result
[3,1,2]	2	4	13	17	false
[4,10,3]	11	33	17	18	true
[3,10,100]	11	1100	13	17	true
[4,100,30]	101	3030	17	18	false
[1,3,1]	4	4	5	7	false

Final output:

[false,true,true,false,false]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N + Q)	One pass to build prefix sums and one pass through queries
Space	O(N)	Prefix sum array requires linear extra space

The prefix sum array is built once in linear time. Each query is then answered in constant time using arithmetic and prefix lookups. This is efficient enough for the problem constraints of 10^5 elements and queries.

Test Cases

from typing import List

class Solution:
    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:
        n = len(candiesCount)

        prefix = [0] * n
        prefix[0] = candiesCount[0]

        for i in range(1, n):
            prefix[i] = prefix[i - 1] + candiesCount[i]

        answer = []

        for favoriteType, favoriteDay, dailyCap in queries:
            min_eaten = favoriteDay + 1
            max_eaten = (favoriteDay + 1) * dailyCap

            candies_before = prefix[favoriteType - 1] if favoriteType > 0 else 0
            candies_up_to = prefix[favoriteType]

            answer.append(
                max_eaten > candies_before and
                min_eaten <= candies_up_to
            )

        return answer

sol = Solution()

# Provided example 1
assert sol.canEat(
    [7,4,5,3,8],
    [[0,2,2],[4,2,4],[2,13,1000000000]]
) == [True, False, True]

# Provided example 2
assert sol.canEat(
    [5,2,6,4,1],
    [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]
) == [False, True, True, False, False]

# Single candy type, day 0 reachable
assert sol.canEat(
    [10],
    [[0,0,1]]
) == [True]  # can eat first candy immediately

# Cannot reach later type soon enough
assert sol.canEat(
    [100,100],
    [[1,0,1]]
) == [False]  # must finish type 0 first

# Large daily cap allows reaching quickly
assert sol.canEat(
    [1,1,1],
    [[2,0,100]]
) == [False]  # still cannot skip earlier types on day 0

# Exact boundary overlap
assert sol.canEat(
    [5],
    [[0,4,1]]
) == [True]  # fifth candy eaten on day 4

# Already exhausted target type
assert sol.canEat(
    [2],
    [[0,5,1]]
) == [False]  # type 0 exhausted before day 5

# Large values stress test
assert sol.canEat(
    [100000] * 100000,
    [[99999, 10**9, 10**9]]
) == [False]

# Multiple mixed queries
assert sol.canEat(
    [3,5,2],
    [[0,1,2],[1,2,2],[2,4,1]]
) == [True, True, False]

Test Case Summary

Test	Why
Example 1	Validates standard mixed outcomes
Example 2	Tests multiple query combinations
Single candy type	Simplest possible input
Cannot reach later type	Ensures ordering rule is enforced
Large daily cap	Verifies cap does not bypass ordering
Exact boundary overlap	Tests interval boundary correctness
Exhausted target type	Ensures late days fail properly
Large values stress test	Verifies performance and overflow safety
Mixed queries	Tests varied scenarios together

Edge Cases

Day Zero Queries

Queries with favoriteDay = 0 are easy to mishandle because only one day of eating has occurred. The implementation correctly computes:

minEaten = 1
maxEaten = dailyCap

This ensures the logic still works for the very first day.

Extremely Large Daily Caps

The value of dailyCap can reach 10^9, and multiplying it by (favoriteDay + 1) can exceed 32-bit integer limits. A naive implementation using regular integers in some languages would overflow.

The Go solution uses int64, and Python naturally supports arbitrary precision integers.

Favorite Type Already Exhausted

A subtle case occurs when the minimum candies eaten by day d already exceeds the last candy index of the target type.

For example:

candiesCount = [2]
query = [0,5,1]

By day 5, at least 6 candies must have been eaten, but only 2 candies of type 0 exist.

The condition:

minEaten <= candiesUpTo

correctly detects this and returns False.

Large Numbers of Queries

Since both candiesCount and queries can contain 10^5 elements, any per-query linear scan would time out.

The prefix sum approach guarantees constant-time query evaluation after preprocessing, making the solution scalable enough for the constraints.