Can You Eat Your Favorite Candy on Your Favorite Day? — LeetCode 1744 Python Solution

The 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].

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.

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

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 1744. Can You Eat Your Favorite Candy on Your Favorite Day? is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems