Problem statement

https://leetcode.com/problems/diet-plan-performance/

Solution

We can find all sums in sliding windows efficiently.

Complexity

Time complexity is O(n), space is O(n) as well. Space can be reduced to O(1).

Code

class Solution:
    def dietPlanPerformance(self, C, k, lower, upper):
        acc, ans = [0] + list(accumulate(C)), 0
        winds = [acc[i+k] - acc[i] for i in range(len(C) + 1 - k)]
        for T in winds:
            if T < lower: ans -= 1
            if T > upper: ans += 1
        return ans