## Saturday, September 28, 2019

### Problem Statement

A dieter consumes `calories[i]` calories on the `i`-th day.
Given an integer `k`, for every consecutive sequence of `k` days (`calories[i], calories[i+1], ..., calories[i+k-1]` for all `0 <= i <= n-k`), they look at T, the total calories consumed during that sequence of `k` days (`calories[i] + calories[i+1] + ... + calories[i+k-1]`):
• If `T < lower`, they performed poorly on their diet and lose 1 point;
• If `T > upper`, they performed well on their diet and gain 1 point;
• Otherwise, they performed normally and there is no change in points.
Initially, the dieter has zero points. Return the total number of points the dieter has after dieting for `calories.length` days.
Note that the total points can be negative.

Example 1:
```Input: calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
Output: 0
Explanation: Since k = 1, we consider each element of the array separately and compare it to lower and upper.
calories and calories are less than lower so 2 points are lost.
calories and calories are greater than upper so 2 points are gained.
```
Example 2:
```Input: calories = [3,2], k = 2, lower = 0, upper = 1
Output: 1
Explanation: Since k = 2, we consider subarrays of length 2.
calories + calories > upper so 1 point is gained.
```
Example 3:
```Input: calories = [6,5,0,0], k = 2, lower = 1, upper = 5
Output: 0
Explanation:
calories + calories > upper so 1 point is gained.
lower <= calories + calories <= upper so no change in points.
calories + calories < lower so 1 point is lost.
```

Constraints:
• `1 <= k <= calories.length <= 10^5`
• `0 <= calories[i] <= 20000`
• `0 <= lower <= upper`

### Video Tutorial

You can find the detailed video tutorial here

### Thought Process

This is an easy problem but might be a bit hard to code it up correctly in one pass. We can use a sliding window to keep a rolling sum and compare it with upper and lower bound.

A few caveats in implementation:
• We can simplify using two pointers start and end by keeping an index i (start) and i - k (end)
• We can only have one loop instead of having two separate loops sliding window

### Solutions

#### Sliding window

Time Complexity: O(N) visited the array once
Space Complexity: O(1) No extra space is needed

• None