Problem Description

A dieter tracks their daily calorie consumption over multiple days. You're given an array calories where calories[i] represents the number of calories consumed on day i.

The dieter evaluates their performance by looking at every consecutive k-day window in their diet. For each window of k consecutive days, they calculate the total calories T consumed during that period.

Based on the total T, they assign points as follows:

• If T < lower: Poor performance, lose 1 point
• If T > upper: Good performance, gain 1 point
• If lower ≤ T ≤ upper: Normal performance, no change in points

The dieter starts with 0 points. Your task is to calculate the final total points after evaluating all possible k-day windows.

For example, if calories = [1,2,3,4,5] and k = 2, you would evaluate:

• Days 0-1: total = 1+2 = 3
• Days 1-2: total = 2+3 = 5
• Days 2-3: total = 3+4 = 7
• Days 3-4: total = 4+5 = 9

Each of these totals would be compared against lower and upper to determine points gained or lost.

The solution uses a prefix sum array to efficiently calculate the sum of any k-day window. The prefix sum s[i] stores the total calories from day 0 to day i-1. This allows us to calculate any window sum as s[i+k] - s[i], which gives the total calories from day i to day i+k-1.

Intuition

The key observation is that we need to calculate the sum of calories for every consecutive k-day window. A naive approach would be to recalculate the sum for each window from scratch, which would involve adding k numbers for each of the n-k+1 windows, resulting in O(n*k) time complexity.

However, we can notice that consecutive windows overlap significantly. For example, if we have windows [day 0, day 1, day 2] and [day 1, day 2, day 3], they share days 1 and 2. Recalculating the entire sum each time is redundant.

This naturally leads us to think about prefix sums - a technique where we precompute cumulative sums. If we know the total calories consumed from day 0 to any day i, we can quickly find the sum of any range.

The prefix sum array s is constructed where s[i] represents the total calories from day 0 to day i-1. With this preprocessing:

• To get the sum from day i to day i+k-1, we simply calculate s[i+k] - s[i]
• This works because s[i+k] contains the sum up to day i+k-1, and s[i] contains the sum up to day i-1
• Subtracting them gives us exactly the calories for days i through i+k-1

This reduces our window sum calculation from O(k) to O(1), making the overall algorithm O(n) after the O(n) preprocessing step. Once we have each window's sum, comparing it with lower and upper to update points is straightforward.

Learn more about Sliding Window patterns.

Solution Approach

The solution implements the prefix sum technique to efficiently calculate the sum of each k-day window.

Step 1: Build the Prefix Sum Array

We use Python's accumulate function with initial=0 to create a prefix sum array s of length n+1:

s = list(accumulate(calories, initial=0))

This creates an array where:

• s[0] = 0 (no calories consumed before day 0)
• s[1] = calories[0]
• s[2] = calories[0] + calories[1]
• s[i] = calories[0] + calories[1] + ... + calories[i-1]

Step 2: Iterate Through All k-Day Windows

We iterate from i = 0 to i = n - k (inclusive), which covers all possible starting positions for a k-day window:

for i in range(n - k + 1):

Step 3: Calculate Window Sum Using Prefix Sum

For each window starting at position i, we calculate the total calories:

t = s[i + k] - s[i]

This gives us the sum of calories[i] + calories[i+1] + ... + calories[i+k-1] in O(1) time.

Step 4: Update Points Based on Performance

We compare the window sum t with the thresholds:

if t < lower:
    ans -= 1
elif t > upper:
    ans += 1

• If t < lower: Subtract 1 point (poor performance)
• If t > upper: Add 1 point (good performance)
• Otherwise: No change (normal performance)

Step 5: Return Final Points

After evaluating all windows, we return the accumulated points ans.

The time complexity is O(n) for building the prefix sum array plus O(n-k+1) for evaluating windows, giving us O(n) overall. The space complexity is O(n) for storing the prefix sum array.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• calories = [3, 2, 5, 1, 4]
• k = 3 (evaluate 3-day windows)
• lower = 6
• upper = 10

Step 1: Build the Prefix Sum Array

We create the prefix sum array s:

• s[0] = 0 (initial value)
• s[1] = 0 + 3 = 3
• s[2] = 3 + 2 = 5
• s[3] = 5 + 5 = 10
• s[4] = 10 + 1 = 11
• s[5] = 11 + 4 = 15

So s = [0, 3, 5, 10, 11, 15]

Step 2-4: Evaluate Each 3-Day Window

Starting with ans = 0:

Window 1: Days 0-2 (calories[0:3] = [3, 2, 5])

• Calculate sum: t = s[0+3] - s[0] = s[3] - s[0] = 10 - 0 = 10
• Compare: 10 is not less than 6 and not greater than 10, so it's in range [6, 10]
• Points: No change, ans = 0

Window 2: Days 1-3 (calories[1:4] = [2, 5, 1])

• Calculate sum: t = s[1+3] - s[1] = s[4] - s[1] = 11 - 3 = 8
• Compare: 8 is in range [6, 10]
• Points: No change, ans = 0

Window 3: Days 2-4 (calories[2:5] = [5, 1, 4])

• Calculate sum: t = s[2+3] - s[2] = s[5] - s[2] = 15 - 5 = 10
• Compare: 10 is in range [6, 10]
• Points: No change, ans = 0

Final Result: The dieter scores 0 points total.

If we had different thresholds, say lower = 7 and upper = 9, the results would be:

• Window 1: t = 10, which is > 9, so ans = 1 (good performance)
• Window 2: t = 8, which is in [7, 9], so ans = 1 (no change)
• Window 3: t = 10, which is > 9, so ans = 2 (good performance)

The prefix sum technique allows us to calculate each window sum in O(1) time instead of repeatedly adding k elements.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the calories array. This is because:

• The accumulate function iterates through all n elements once to build the prefix sum array, which takes O(n) time
• The for loop iterates n - k + 1 times, which is O(n) in the worst case
• Each iteration of the loop performs constant time operations: array lookups, subtraction, and comparisons
• Therefore, the overall time complexity is O(n) + O(n) = O(n)

The space complexity is O(n), where n is the length of the calories array. This is because:

• The prefix sum array s stores n + 1 elements (including the initial 0), requiring O(n) space
• The other variables (ans, n, i, t) use constant space O(1)
• Therefore, the overall space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Errors in Window Iteration

Pitfall: A common mistake is incorrectly calculating the range for iterating through k-day windows. Developers might write:

• range(n - k) instead of range(n - k + 1), which misses the last valid window
• range(n) which causes index out of bounds when accessing prefix_sums[i + k]

Example of the mistake:

# WRONG: Misses the last valid window
for i in range(len(calories) - k):  # Should be len(calories) - k + 1
    window_sum = prefix_sums[i + k] - prefix_sums[i]

Solution: Always use range(n - k + 1) where n is the length of the calories array. This ensures you check all valid windows including the last one.

2. Incorrect Prefix Sum Indexing

Pitfall: Confusion about prefix sum array indexing, especially when not using initial=0. Without the initial zero, developers might incorrectly calculate window sums.

Example of the mistake:

# WRONG: Without initial=0, indexing becomes confusing
prefix_sums = list(accumulate(calories))  # No initial=0
# Now prefix_sums[i] represents sum up to and including calories[i]
# This requires different indexing logic:
window_sum = prefix_sums[i + k - 1] - (prefix_sums[i - 1] if i > 0 else 0)

Solution: Always use accumulate(calories, initial=0) to maintain consistent indexing where prefix_sums[i] represents the sum of the first i elements, making the window sum calculation straightforward: prefix_sums[i + k] - prefix_sums[i].

3. Edge Case: k Equals Array Length

Pitfall: Not handling the case where k equals the length of the calories array properly, or assuming there will always be multiple windows to evaluate.

Example scenario:

calories = [100, 200, 300]
k = 3  # Only one window possible

Solution: The code naturally handles this case when using range(n - k + 1), which becomes range(1), evaluating exactly one window. However, always verify this edge case in testing.

4. Misunderstanding Threshold Comparisons

Pitfall: Using incorrect comparison operators or including equality in the wrong conditions.

Example of the mistake:

# WRONG: Including equality in both conditions
if window_sum <= lower:  # Should be < lower
    score -= 1
elif window_sum >= upper:  # Should be > upper
    score += 1

Solution: Remember the exact conditions:

• Lose point: window_sum < lower (strictly less than)
• Gain point: window_sum > upper (strictly greater than)
• No change: lower <= window_sum <= upper (inclusive range)