1744. Can You Eat Your Favorite Candy on Your Favorite Day?

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

You are given a (0-indexed) array of positive integers candiesCount where candiesCount[i] represents the number of candies of the i^th type you have. You are also given a 2D array queries where queries[i] = [favoriteType_i, favoriteDay_i, dailyCap_i].

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 favoriteType_i on day favoriteDay_i without eating more than dailyCap_i 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 <= 10⁵
1 <= candiesCount[i] <= 10⁵
1 <= queries.length <= 10⁵
queries[i].length == 3
0 <= favoriteType_i < candiesCount.length
0 <= favoriteDay_i <= 10⁹
1 <= dailyCap_i <= 10⁹

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.

Python

from typing import List

class Solution:
    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:
        prefix_sum = [0] * (len(candiesCount) + 1)
        for i in range(len(candiesCount)):
            prefix_sum[i + 1] = prefix_sum[i] + candiesCount[i]
        result = []
        for query in queries:
            favoriteType, favoriteDay, dailyCap = query
            min_candies = favoriteDay + 1
            max_candies = (favoriteDay + 1) * dailyCap
            can_eat = max_candies > prefix_sum[favoriteType] and min_candies <= prefix_sum[favoriteType + 1]
            result.append(can_eat)
        return result

Java

import java.util.*;

class Solution {
    public boolean[] canEat(int[] candiesCount, int[][] queries) {
        int n = candiesCount.length;
        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; ++i) {
            prefixSum[i + 1] = prefixSum[i] + candiesCount[i];
        }
        boolean[] result = new boolean[queries.length];
        for (int i = 0; i < queries.length; ++i) {
            int favoriteType = queries[i][0];
            long favoriteDay = queries[i][1];
            long dailyCap = queries[i][2];
            long minCandies = favoriteDay + 1;
            long maxCandies = (favoriteDay + 1) * dailyCap;
            result[i] = maxCandies > prefixSum[favoriteType] && minCandies <= prefixSum[favoriteType + 1];
        }
        return result;
    }
}

C++

#include <vector>
using namespace std;

vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
    int n = candiesCount.size();
    vector<long long> prefixSum(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefixSum[i + 1] = prefixSum[i] + candiesCount[i];
    }
    vector<bool> result;
    for (const auto& q : queries) {
        int favoriteType = q[0];
        long long favoriteDay = q[1];
        long long dailyCap = q[2];
        long long minCandies = favoriteDay + 1;
        long long maxCandies = (favoriteDay + 1) * dailyCap;
        bool can = maxCandies > prefixSum[favoriteType] && minCandies <= prefixSum[favoriteType + 1];
        result.push_back(can);
    }
    return result;
}

JavaScript

var canEat = function(candiesCount, queries) {
    const prefixSum = new Array(candiesCount.length + 1).fill(0);
    for (let i = 0; i < candiesCount.length; ++i) {
        prefixSum[i + 1] = prefixSum[i] + candiesCount[i];
    }
    const result = [];
    for (let i = 0; i < queries.length; ++i) {
        const [favoriteType, favoriteDay, dailyCap] = queries[i];
        const minCandies = favoriteDay + 1;
        const maxCandies = (favoriteDay + 1) * dailyCap;
        result.push(maxCandies > prefixSum[favoriteType] && minCandies <= prefixSum[favoriteType + 1]);
    }
    return result;
};

#include <stdlib.h>
#include <stdbool.h>

bool* canEat(int* candiesCount, int candiesCountSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    long long* prefixSum = (long long*)malloc(sizeof(long long) * (candiesCountSize + 1));
    prefixSum[0] = 0;
    for (int i = 0; i < candiesCountSize; ++i) {
        prefixSum[i + 1] = prefixSum[i] + candiesCount[i];
    }

    bool* result = (bool*)malloc(sizeof(bool) * queriesSize);
    for (int i = 0; i < queriesSize; ++i) {
        int favoriteType = queries[i][0];
        long long favoriteDay = queries[i][1];
        long long dailyCap = queries[i][2];

        long long minCandies = favoriteDay + 1;
        long long maxCandies = (favoriteDay + 1) * dailyCap;

        result[i] = maxCandies > prefixSum[favoriteType] && minCandies <= prefixSum[favoriteType + 1];
    }

    free(prefixSum);
    *returnSize = queriesSize;
    return result;
}

public class Solution {
    public bool[] CanEat(int[] candiesCount, int[][] queries) {
        long[] prefixSum = new long[candiesCount.Length + 1];
        for (int i = 0; i < candiesCount.Length; ++i) {
            prefixSum[i + 1] = prefixSum[i] + candiesCount[i];
        }
        bool[] result = new bool[queries.Length];
        for (int i = 0; i < queries.Length; ++i) {
            int favoriteType = queries[i][0];
            long favoriteDay = queries[i][1];
            long dailyCap = queries[i][2];
            long minCandies = favoriteDay + 1;
            long maxCandies = (favoriteDay + 1) * dailyCap;
            result[i] = maxCandies > prefixSum[favoriteType] && minCandies <= prefixSum[favoriteType + 1];
        }
        return result;
    }
}

The Python solution makes use of a prefix sum to identify if it's feasible to consume a candy of the desired type by a particular day. Queries check the feasible range of consumption against candy availability.

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.

Python

from typing import List

class Solution:
    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:
        result = []
        for query in queries:
            favoriteType, favoriteDay, dailyCap = query
            max_candies = sum(candiesCount[:favoriteType+1])
            min_candies = 1 if favoriteType == 0 else sum(candiesCount[:favoriteType]) + 1
            can_eat = (favoriteDay + 1) * dailyCap >= min_candies and favoriteDay + 1 <= max_candies
            result.append(can_eat)
        return result

Java

import java.util.*;

class Solution {
    public boolean[] canEat(int[] candiesCount, int[][] queries) {
        boolean[] result = new boolean[queries.length];
        for (int i = 0; i < queries.length; ++i) {
            int favoriteType = queries[i][0];
            long favoriteDay = queries[i][1];
            long dailyCap = queries[i][2];
            long maxCandies = 0;
            for (int j = 0; j <= favoriteType; ++j) {
                maxCandies += candiesCount[j];
            }
            long minCandies = favoriteDay + 1;
            result[i] = maxCandies >= minCandies && favoriteDay + 1 <= maxCandies;
        }
        return result;
    }
}

C++

#include <vector>
using namespace std;

vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
    vector<bool> result;
    for (const auto& query : queries) {
        int favoriteType = query[0];
        long long favoriteDay = query[1];
        long long dailyCap = query[2];
        long long maxCandies = 0;
        for (int i = 0; i <= favoriteType; ++i) {
            maxCandies += candiesCount[i];
        }
        long long minCandies = max(1LL, favoriteDay + 1 - candiesCount[favoriteType]);
        bool canEatMilkshake = (favoriteDay + 1) * dailyCap >= minCandies && favoriteDay + 1 <= maxCandies;
        result.push_back(canEatMilkshake);
    }
    return result;
}

JavaScript

var canEat = function(candiesCount, queries) {
    const result = [];
    for (const [favoriteType, favoriteDay, dailyCap] of queries) {
        let totalCandies = 0;
        for (let i = 0; i <= favoriteType; ++i) {
            totalCandies += candiesCount[i];
        }
        const minCandies = favoriteDay + 1;
        const maxCandies = (favoriteDay + 1) * dailyCap;
        result.push(maxCandies >= minCandies && favoriteDay + 1 <= totalCandies);
    }
    return result;
};

#include <stdlib.h>
#include <stdbool.h>

bool* canEat(int* candiesCount, int candiesCountSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    bool* result = (bool*)malloc(sizeof(bool) * queriesSize);
    for (int i = 0; i < queriesSize; ++i) {
        int favoriteType = queries[i][0];
        int favoriteDay = queries[i][1];
        int dailyCap = queries[i][2];
        long long totalCandies = 0;
        for (int j = 0; j <= favoriteType; j++) {
            totalCandies += candiesCount[j];
        }
        long long minCandiesToEat = favoriteType == 0 ? 1 : totalCandies - candiesCount[favoriteType] + 1;
        result[i] = (favoriteDay + 1) * dailyCap >= minCandiesToEat && favoriteDay + 1 <= totalCandies;
    }
    *returnSize = queriesSize;
    return result;
}

public class Solution {
    public bool[] CanEat(int[] candiesCount, int[][] queries) {
        bool[] result = new bool[queries.Length];
        for (int i = 0; i < queries.Length; ++i) {
            int favoriteType = queries[i][0];
            long favoriteDay = queries[i][1];
            long dailyCap = queries[i][2];
            long totalCandies = 0;
            for (int j = 0; j <= favoriteType; ++j) {
                totalCandies += candiesCount[j];
            }
            long minCandies = favoriteDay + 1;
            result[i] = totalCandies >= minCandies && favoriteDay + 1 <= totalCandies;
        }
        return result;
    }
}

Python achieves direct simulation by assessing the permissible range of candies for each query, confirming feasible eating by checking against possible candy intake limits per day.

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

func canEat(candiesCount []int, queries [][]int) (ans []bool) {
	n := len(candiesCount)
	s := make([]int, n+1)
	for i, v := range candiesCount {
		s[i+1] = s[i] + v
	}
	for _, q := range queries {
		t, day, mx := q[0], q[1], q[2]
		least, most := day, (day+1)*mx
		ans = append(ans, least < s[t+1] && most > s[t])
	}
	return
}

Try this approach in the editor

Complexity comparison

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	–

Complexity analysis

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

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.

Can You Eat Your Favorite Candy on Your Favorite Day? solution and explanation

The problem

Approach overview

Approach 1: Prefix Sum Calculation

Approach 2: Direct Simulation

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Can You Eat Your Favorite Candy on Your Favorite Day? solution and explanation

The problem

Approach overview

Approach 1: Prefix Sum Calculation

Approach 2: Direct Simulation

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems