# Can You Eat Your Favorite Candy on Your Favorite Day?
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/can-you-eat-your-favorite-candy-on-your-favorite-day)
Canonical: https://scaleengineer.com/dsa/problems/can-you-eat-your-favorite-candy-on-your-favorite-day
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## Problem
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`

# Approaches
## Brute Force Calculation for Each Query
This approach processes each query independently without any pre-computation. For every query, it iterates through the `candiesCount` array to calculate the necessary cumulative sums of candies required to determine if the conditions can be met.
**Time:** O(Q * N), where Q is the number of queries and N is the length of `candiesCount`. For each of the Q queries, we might iterate up to N times to calculate `candiesBefore`. · **Space:** O(Q) or O(1), depending on whether the output array is counted. Excluding the output array, the space complexity is O(1).
**Pros:** Simple to understand and implement.; Low space complexity as it doesn't require any auxiliary data structures that scale with the input size `N`.
**Cons:** Inefficient time complexity. For each query, it re-calculates the sum of candies, leading to redundant computations if multiple queries ask about types with high indices.
### Explanation
For each query `[favoriteType, favoriteDay, dailyCap]`, we need to determine if it's possible to be eating a candy of type `favoriteType` on `favoriteDay`.

This is possible if and only if two conditions are met:
1.  You can reach the *first* candy of `favoriteType` by `favoriteDay`. This means the maximum number of candies you could possibly eat by the end of `favoriteDay` must be greater than the total number of candies of all preceding types.
2.  You have not finished *all* candies of `favoriteType` *before* `favoriteDay`. This means the minimum number of candies you must eat by the end of `favoriteDay` must be less than or equal to the total number of candies up to and including `favoriteType`.

Let's formalize the conditions:
*   Let `candiesBefore` be the total number of candies of types `0` to `favoriteType - 1`. We calculate this by summing up `candiesCount[i]` for `i` from `0` to `favoriteType - 1`.
*   Let `candiesIncluding` be the total number of candies of types `0` to `favoriteType`. This is `candiesBefore + candiesCount[favoriteType]`.
*   **Condition 1 (Earliest possible day):** To start eating `favoriteType` candies, you must first finish all `candiesBefore`. The maximum number of candies you can eat per day is `dailyCap`. After `favoriteDay + 1` days (from day 0 to `favoriteDay`), the maximum total candies you can eat is `(favoriteDay + 1) * dailyCap`. To be able to eat a candy of `favoriteType`, this maximum must be at least one more than `candiesBefore`. So, `(favoriteDay + 1) * dailyCap > candiesBefore`.
*   **Condition 2 (Latest possible day):** You must eat at least one candy per day. After `favoriteDay + 1` days, you will have eaten at least `favoriteDay + 1` candies. To still be able to eat a candy of `favoriteType` on `favoriteDay`, you must not have finished all of them. This means the total number of candies up to `favoriteType`, `candiesIncluding`, must be greater than or equal to the minimum number of candies you have eaten. So, `candiesIncluding >= favoriteDay + 1`.

The algorithm iterates through each query, calculates `candiesBefore` and `candiesIncluding` from scratch, and then checks these two conditions. It's important to use 64-bit integers (`long` in Java) for candy counts to avoid overflow.

```java
class Solution {
    public boolean[] canEat(int[] candiesCount, int[][] queries) {
        boolean[] answer = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int type = queries[i][0];
            int day = queries[i][1];
            int cap = queries[i][2];

            long candiesBefore = 0;
            for (int j = 0; j < type; j++) {
                candiesBefore += candiesCount[j];
            }
            
            long candiesIncluding = candiesBefore + candiesCount[type];

            // Condition 1: Can we reach the first candy of this type in time?
            long maxCandiesEaten = (long)(day + 1) * cap;
            boolean canReach = maxCandiesEaten > candiesBefore;

            // Condition 2: Have we already finished all candies of this type before this day?
            long minCandiesEaten = day + 1;
            boolean notFinished = minCandiesEaten <= candiesIncluding;

            answer[i] = canReach && notFinished;
        }
        return answer;
    }
}
```
### Algorithm
- Initialize a boolean array `answer` of the same size as `queries`.
- Loop through each query `q` at index `i` in `queries`:
  - Extract `type = q[0]`, `day = q[1]`, `cap = q[2]`.
  - Initialize `candiesBefore = 0L`.
  - Loop `j` from `0` to `type - 1`:
    - `candiesBefore += candiesCount[j]`.
  - Calculate `candiesIncluding = candiesBefore + candiesCount[type]`.
  - Check the first condition: `(day + 1L) * cap > candiesBefore`.
  - Check the second condition: `day + 1L <= candiesIncluding`.
  - If both conditions are true, set `answer[i] = true`. Otherwise, set `answer[i] = false`.
- Return `answer`.

## Optimized Approach with Prefix Sums
This approach significantly improves performance by pre-calculating the cumulative sums of candies. By creating a prefix sum array, we can find the total number of candies before any given type in constant time, O(1). This avoids the costly re-computation for each query.
**Time:** O(N + Q), where N is the length of `candiesCount` and Q is the number of queries. O(N) for building the prefix sum array and O(Q) for processing all queries (O(1) per query). · **Space:** O(N) to store the prefix sum array, where N is the length of `candiesCount`.
**Pros:** Highly efficient time complexity, making it suitable for large inputs.; The logic is straightforward once the concept of prefix sums is applied.
**Cons:** Requires extra space for the prefix sum array, which might be a concern in extremely memory-constrained environments.
### Explanation
The core logic for determining if a query is satisfiable remains the same as the brute-force approach. The possibility still hinges on two conditions: being able to reach the desired candy type in time and not having already finished all candies of that type. The innovation here is how we calculate the number of candies efficiently.

We first create a prefix sum array, let's call it `prefixSum`, of size `candiesCount.length + 1`. `prefixSum[i]` will store the total number of candies of types `0` through `i-1`.
*   `prefixSum[0]` is initialized to 0.
*   `prefixSum[i] = prefixSum[i-1] + candiesCount[i-1]` for `i > 0`.

This pre-computation takes O(N) time, where N is the number of candy types. It's crucial to use 64-bit integers (`long` in Java) for the prefix sum array to prevent potential overflow.

Once the `prefixSum` array is built, we can answer each query in O(1) time. For a query `[favoriteType, favoriteDay, dailyCap]`:
*   The number of candies before `favoriteType` is simply `prefixSum[favoriteType]`.
*   The total number of candies up to and including `favoriteType` is `prefixSum[favoriteType + 1]`.
*   We then apply the same two conditions as before:
    1.  `(favoriteDay + 1L) * dailyCap > prefixSum[favoriteType]`
    2.  `favoriteDay + 1L <= prefixSum[favoriteType + 1]`

This method drastically reduces the overall time complexity by trading a small amount of extra space.

```java
class Solution {
    public boolean[] canEat(int[] candiesCount, int[][] queries) {
        int n = candiesCount.length;
        
        // Step 1: Create prefix sum array. Use long to avoid overflow.
        long[] prefixSum = new long[n + 1];
        prefixSum[0] = 0;
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + candiesCount[i];
        }

        boolean[] answer = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int type = queries[i][0];
            int day = queries[i][1];
            int cap = queries[i][2];

            long candiesBefore = prefixSum[type];
            long candiesIncluding = prefixSum[type + 1];

            // Condition 1: Can we reach the first candy of this type in time?
            long maxCandiesEaten = (long)(day + 1) * cap;
            boolean canReach = maxCandiesEaten > candiesBefore;

            // Condition 2: Have we already finished all candies of this type before this day?
            long minCandiesEaten = day + 1;
            boolean notFinished = minCandiesEaten <= candiesIncluding;

            answer[i] = canReach && notFinished;
        }
        
        return answer;
    }
}
```
### Algorithm
- Create a `long` array `prefixSum` of size `candiesCount.length + 1`.
- Initialize `prefixSum[0] = 0`.
- Loop `i` from `1` to `candiesCount.length`:
  - `prefixSum[i] = prefixSum[i-1] + candiesCount[i-1]`.
- Initialize a boolean array `answer` of the same size as `queries`.
- Loop through each query `q` at index `i` in `queries`:
  - Extract `type = q[0]`, `day = q[1]`, `cap = q[2]`.
  - Get `candiesBefore = prefixSum[type]`.
  - Get `candiesIncluding = prefixSum[type + 1]`.
  - Check the first condition: `(day + 1L) * cap > candiesBefore`.
  - Check the second condition: `day + 1L <= candiesIncluding`.
  - If both conditions are true, set `answer[i] = true`. Otherwise, set `answer[i] = false`.
- Return `answer`.

# Solutions
### Java

```java
class Solution {
public
  boolean[] canEat(int[] candiesCount, int[][] queries) {
    int n = candiesCount.length;
    long[] s = new long[n + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + candiesCount[i];
    }
    int m = queries.length;
    boolean[] ans = new boolean[m];
    for (int i = 0; i < m; ++i) {
      int t = queries[i][0], day = queries[i][1], mx = queries[i][2];
      long least = day, most = (long)(day + 1) * mx;
      ans[i] = least < s[t + 1] && most > s[t];
    }
    return ans;
  }
}

```

### CPP

```cpp
using ll = long long ; class Solution { public: vector < bool > canEat ( vector < int >& candiesCount , vector < vector < int >>& queries ) { int n = candiesCount . size (); vector < ll > s ( n + 1 ); for ( int i = 0 ; i < n ; ++ i ) s [ i + 1 ] = s [ i ] + candiesCount [ i ]; vector < bool > ans ; for ( auto & q : queries ) { int t = q [ 0 ], day = q [ 1 ], mx = q [ 2 ]; ll least = day , most = 1ll * ( day + 1 ) * mx ; ans . emplace_back ( least < s [ t + 1 ] && most > s [ t ]); } return ans ; } };
```

### Python

```python
class Solution:
    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]: s = list(accumulate(candiesCount, initial=0)) ans = [] for t, day, mx in queries: least, most = day, (day + 1) * mx ans . append(least < s[t + 1] and most > s[t]) return ans

```