Leetcode #1744: Can You Eat Your Favorite Candy on Your Favorite Day?
In this guide, we solve Leetcode #1744 Can You Eat Your Favorite Candy on Your Favorite Day? in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
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].
Quick Facts
- Difficulty: Medium
- Premium: No
- Tags: Array, Prefix Sum
Intuition
Range queries become simple once we precompute cumulative sums.
We can transform subarray conditions into prefix comparisons.
Approach
Compute prefix sums and use a map to find matching prefixes.
This avoids nested loops while keeping the logic clear.
Steps:
- Compute prefix sums.
- Use a map to find valid ranges.
- Update the answer.
Example
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.
Python Solution
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
Complexity
The time complexity is O(n). The space complexity is O(n).
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.