Can You Eat Your Favorite Candy on Your Favorite Day: Prefix Sum Range Check

You are given a 0-indexed array candiesCount where candiesCount[i] is the number of candies of type i. You are also given a list of queries where each query is [favoriteType, favoriteDay, dailyCap]. For each query, determine if you can eat a candy of type favoriteType on day favoriteDay, given that you eat between 1 and dailyCap candies per day (starting from day 0) and you must eat all candies of type i before eating any candy of type i + 1.

This is LeetCode 1744: Can You Eat Your Favorite Candy on Your Favorite Day?, and it is a clean example of how prefix sums combine with range overlap checks to answer queries in constant time.

Why this problem matters

At first glance this problem seems like a simulation. You might be tempted to walk through the days one by one, tracking which candy type you are on. But with potentially millions of queries and millions of candies, simulation would be far too slow.

The real lesson here is that prefix sums can turn cumulative counting problems into range queries. Once you precompute the total number of candies before each type, every query reduces to a single overlap check between two intervals. This pattern appears in scheduling problems, resource allocation, and any scenario where you need to check if a range of possible values intersects a known interval.

If you have worked through prefix sum basics on problems like Range Sum Query or Subarray Sum Equals K, this problem shows you a different flavor: instead of summing within a range, you are checking whether two derived ranges overlap.

The key insight

The trick is to realize that both the number of candies you could have eaten by day d and the index range of your favorite candy type can be expressed as intervals. Then the answer is simply whether those intervals overlap.

First, build a prefix sum array so that prefix[i] is the total number of candies in types 0 through i - 1. The candies of type t occupy positions prefix[t] + 1 through prefix[t + 1] in the overall candy sequence.

Second, by day d (0-indexed), you have eaten on days 0, 1, ..., d, which is d + 1 days total. The minimum number of candies you could have eaten is d + 1 (eating 1 per day). The maximum is (d + 1) * cap (eating cap per day).

If the interval [d + 1, (d + 1) * cap] overlaps with [prefix[t] + 1, prefix[t + 1]], then there exists some eating strategy that lands you on a candy of type t on day d. Two intervals [a, b] and [c, d] overlap when a <= d and c <= b.

The solution

def can_eat(candiesCount, queries):
    n = len(candiesCount)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + candiesCount[i]

    result = []
    for t, d, cap in queries:
        eat_min = d + 1
        eat_max = (d + 1) * cap
        type_min = prefix[t] + 1
        type_max = prefix[t + 1]
        result.append(eat_min <= type_max and type_min <= eat_max)

    return result

The first loop builds the prefix sum array in O(n) time. prefix[0] is 0, and each subsequent entry accumulates the candy count. After this step, prefix[t] holds the total number of candies in types 0 through t - 1.

For each query, we compute two ranges. The "eat range" [d + 1, (d + 1) * cap] represents the minimum and maximum total candies you could have eaten through day d. The "type range" [prefix[t] + 1, prefix[t + 1]] represents which candies (by global index) belong to type t.

The overlap check eat_min <= type_max and type_min <= eat_max is the standard formula for testing whether two closed intervals intersect. If they do, some valid eating strategy lets you eat a candy of type t on exactly day d.

Visual walkthrough

Let's trace through three queries on candiesCount = [7, 4, 5, 3, 8] with prefix = [0, 7, 11, 16, 19, 27]. For each query, we compute the eat range and the type range, then check if they overlap.

Notice the pattern: when the query asks about a late day with a small cap, you may have already eaten past the target type (eat range is entirely above the type range). When the query asks about an early day for a high-numbered type, you cannot eat fast enough to reach it (eat range is entirely below the type range). The overlap check catches both cases cleanly.

Complexity analysis

Time is O(n + q) where n is the length of candiesCount and q is the number of queries. Building the prefix array takes O(n). Each query is answered in O(1) with a constant-time overlap check. Total: O(n + q).

Space is O(n) for the prefix sum array. The result array is O(q) but that is required for the output. The prefix array is the only auxiliary space.

The building blocks

1. Prefix sum construction

The foundation of the approach is building a running total so you can answer "how many candies are in types 0 through t?" in O(1):

prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + candiesCount[i]

This is the same prefix sum array used in Range Sum Query. Once built, prefix[j] - prefix[i] gives the total candies in types i through j - 1. Here we use it to find the start and end indices of each candy type in the global candy sequence.

2. Interval overlap check

The second building block is the constant-time test for whether two closed intervals intersect:

overlap = (a <= d) and (c <= b)

Two intervals [a, b] and [c, d] overlap if and only if neither one is entirely to the left of the other. The condition "a is at most d, and c is at most b" captures this precisely. You will reuse this pattern in merge intervals, meeting rooms, and any problem that asks whether ranges intersect.

Edge cases

• Day 0 with type 0: eat range is [1, cap], type range is [1, candiesCount[0]]. Always true as long as candiesCount[0] >= 1.
• Daily cap of 1: eat range collapses to [d + 1, d + 1]. You eat exactly one candy per day, so the question is whether candy number d + 1 falls in the target type's range.
• Very large day: if d + 1 exceeds the total number of all candies, you run out of candy before reaching that day. But the overlap check still works because eat_min will exceed type_max for any type.
• Single candy type: prefix = [0, total]. The only valid days are 0 through total - 1 (you need to still have candy left on day d, and you start eating on day 0).
• Large daily cap with early day: eat_max can be huge, but as long as eat_min (d + 1) is at most prefix[t + 1], you are fine. You do not have to eat your maximum each day.

From understanding to recall

You now see how prefix sums and a simple overlap check solve this problem. The algorithm is short and the logic is clean. But the devil is in the details: off-by-one errors in the ranges, remembering that days are 0-indexed, and correctly computing d + 1 instead of d. These are the mistakes that surface under interview pressure.

Spaced repetition is how you make the details automatic. You practice writing the prefix sum construction and the overlap condition from memory. After a few repetitions, you stop second-guessing whether the eat range starts at d or d + 1. You stop hesitating over whether prefix[t] or prefix[t] + 1 is the lower bound. The pattern flows out correctly because you have written it correctly before.

Related posts

• Subarray Sum Equals K - Another prefix sum problem that uses cumulative sums to answer range queries
• Product of Array Except Self - Uses prefix and suffix products, a related accumulation technique
• Range Sum Query - The foundational prefix sum problem for range queries

CodeBricks breaks Can You Eat Your Favorite Candy on Your Favorite Day into its prefix sum construction and interval overlap building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a prefix sum problem shows up in your interview, you do not think about it. You just write it.