#1744
Can You Eat Your Favorite Candy on Your Favorite Day?
MediumArrayPrefix SumPrefix SumArray
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n + q) |
| Space | O(1) | O(n) |
💡
Intuition
Time O(n + q)Space O(n)
The optimal approach calculates the earliest and latest possible days to eat the favorite candy type based on the daily cap and total candies. This avoids simulating each day and directly computes the results for each query.
⚙️
Algorithm
3 steps- 1Step 1: Precompute the prefix sum of candiesCount to quickly find the total candies eaten before each type.
- 2Step 2: For each query, determine the earliest and latest day to eat the favorite candy type using the prefix sum.
- 3Step 3: Check if the favorite day falls within the calculated earliest and latest days.
solution.py11 lines
1def canEat(candiesCount, queries):
2 prefixSum = [0] * len(candiesCount)
3 prefixSum[0] = candiesCount[0]
4 for i in range(1, len(candiesCount)):
5 prefixSum[i] = prefixSum[i - 1] + candiesCount[i]
6 answer = []
7 for favoriteType, favoriteDay, dailyCap in queries:
8 earliestDay = (prefixSum[favoriteType] - candiesCount[favoriteType] + 1 + dailyCap - 1) // dailyCap
9 latestDay = prefixSum[favoriteType] // dailyCap
10 answer.append(earliestDay <= favoriteDay <= latestDay)
11 return answerℹ
Complexity note: The time complexity is O(n + q) where n is the number of candy types and q is the number of queries. We compute the prefix sum in O(n) and then answer each query in O(1).
- 1The earliest day to eat a favorite candy is determined by the total candies eaten before it and the daily cap.
- 2The latest day is simply the total candies eaten up to that type divided by the daily cap.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.