---
# System prepended metadata

title: Prefix sum

---

# Prefix sum


## Slow solution
```python=
class Solution:
    def canEat(self, candiesCount: list[int], queries: list[list[int]]) -> list[bool]:
        # init boolean array of queries length.
        answer = len(queries) * [False]
        
        for ix, query in enumerate(queries):
            favoriteType = query[0]
            favoriteDay = query[1]
            favoriteCap = query[2]
            
            min = 0 if (favoriteCap == 0) else (favoriteDay + 1)
            max = (favoriteDay + 1) * favoriteCap
            
            candiesCount_min = 0
            candiesCount_max = 0
            
            for index, candies in enumerate(candiesCount[:(favoriteType + 1)]):
                if (index != 0):
                    candiesCount_min = candiesCount_min + candiesCount[index -1] + 1
                candiesCount_max = candiesCount_max + candies
                
            # Max can never be lower than min           
            if (candiesCount_min > candiesCount_max):
                pass                
            elif (min <= candiesCount_min) and (max >= candiesCount_min):
                answer[ix] = True
            elif (min <= candiesCount_max) and (max >= candiesCount_max):
                answer[ix] = True
            elif (min >= candiesCount_min) and (max <= candiesCount_max):
                answer[ix] = True
        
        return answer
```

## Faster solution
Create a summed up array instead and retrieve ranges.


```python=
class Solution:
    def canEat(self, candiesCount: list[int], queries: list[list[int]]) -> list[bool]:
        # init boolean array of queries length.
        answer = len(queries) * [False]
        
        # create (prefix) sum array to retrieve in O(1) time in loop
        sum_array = len(candiesCount) * [0]       
        for index, candies in enumerate(candiesCount):
            if (index == 0): 
                sum_array[index] = candies
            else:
                sum_array[index] = candies + sum_array[index -1]
        
        for ix, query in enumerate(queries):
            favoriteType = query[0]
            favoriteDay = query[1]
            dailyCap = query[2]
            
            min = 0 if (dailyCap == 0) else (favoriteDay + 1)
            max = (favoriteDay + 1) * dailyCap 
                      
            candiesCount_min = 0 if (favoriteType - 1) == -1 else sum_array[(favoriteType - 1)]
            candiesCount_max = sum_array[favoriteType]
                
            # Max can never be lower than min           
            if (candiesCount_min > candiesCount_max):
                pass                
            elif (min <= candiesCount_min) and (max >= candiesCount_min):
                answer[ix] = True
            elif (min <= candiesCount_max) and (max >= candiesCount_max):
                answer[ix] = True
            elif (min >= candiesCount_min) and (max <= candiesCount_max):
                answer[ix] = True
        
        return answer
```