Can you eat your favorite candy on your favorite day
December 7, 2022
array-and-hashmapProblem URL: Can you eat your favorite candy on your favorite day
Define a prefix sum of candiesCount. If you label all candies starting from 1 and order them by type:
- [prefix[candyType]+1, prefix[candyType+1]] are all the candies of type candyType.
- At minimum, you must eat targetDay+1 candies.
- At maximum, you can eat (targetDay+1)*dailyCap
- So now you have two intervals. The answer to each query is whether or not these two intervals overlap.
class Solution:
def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:
prefix = [0]
for candy in candiesCount:
prefix.append(prefix[-1]+candy)
def helper(candyType, targetDay, dailyCap):
low, high = prefix[candyType]+1, prefix[candyType+1]
minEat = targetDay+1
maxEat = (targetDay+1)*dailyCap
if maxEat < low or minEat > high:
return False
else:
return True
res = [helper(*query) for query in queries]
return res
Time complexity: O(n)
Space complexity: O(n)