Diet Plan Performance — Fixed Sliding Window of Size K at Google

Problem Statement#

A dieter consumes calories[i] calories on the i-th day. Given an integer k, for every consecutive sequence of k days, compare the total calories T to lower and upper. If T < lower, lose 1 point; if T > upper, gain 1 point; otherwise no change. Return the total points after evaluating all such sequences.

Constraints:

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

Input:  calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
Output: 0

Input:  calories = [3,2], k = 2, lower = 0, upper = 1
Output: 1

Why This Problem Matters#

LeetCode 1176 Diet Plan Performance is the cleanest fixed sliding window problem on LeetCode. Google uses it as a phone screen warm-up because it forces candidates to maintain a running sum across consecutive windows of fixed size k, the foundation for every fixed-window problem.

The brute force is O(n * k) and recomputes the sum for each window. The sliding window optimization runs in O(n) by adding the new element and subtracting the element falling out of the window.

This problem prepares you for LC 643 Maximum Average Subarray I, LC 1456 Maximum Number of Vowels in a Substring of Given Length, and any "fixed window of size k" question.

The Core Insight#

A fixed-size window can be slid one step at a time by adding the incoming element and subtracting the outgoing element. The first window is filled by summing the first k elements; every subsequent window updates the sum in O(1).

For each window we compare the sum to lower and upper and update the points accordingly. The window count is n - k + 1, so the total work is O(n).

The invariant is simple: at the start of iteration i for i >= k - 1, window_sum equals the sum of calories[i - k + 1 ... i].

Visual Dry Run#

For calories = [3, 2], k = 2, lower = 0, upper = 1:

For calories = [1, 2, 3, 4, 5], k = 3, lower = 5, upper = 10:

Solution (Optimal)#

class Solution:
    def dietPlanPerformance(self, calories: list[int], k: int, lower: int, upper: int) -> int:
        window_sum = sum(calories[:k])
        points = 0
        if window_sum < lower:
            points -= 1
        elif window_sum > upper:
            points += 1
        for i in range(k, len(calories)):
            window_sum += calories[i] - calories[i - k]
            if window_sum < lower:
                points -= 1
            elif window_sum > upper:
                points += 1
        return points

var dietPlanPerformance = function(calories, k, lower, upper) {
    let windowSum = 0;
    for (let i = 0; i < k; i++) windowSum += calories[i];
    let points = 0;
    if (windowSum < lower) points--;
    else if (windowSum > upper) points++;
    for (let i = k; i < calories.length; i++) {
        windowSum += calories[i] - calories[i - k];
        if (windowSum < lower) points--;
        else if (windowSum > upper) points++;
    }
    return points;
};

Time: O(n) — initial fill plus single pass over the rest Space: O(1) — one running sum

Common Mistakes#

• Recomputing the window sum from scratch each step, costing O(n * k)
• Forgetting to evaluate the first window before the slide loop
• Off-by-one when computing the index of the element to remove (i - k not i - k + 1)
• Using < and > strictly when the problem allows equality with lower and upper
• Mistaking this for a variable window because the problem says consecutive sequence

Interview Tips#

• Say "fixed window of size k" out loud; the problem statement uses "consecutive sequence of k days" which is the same thing
• Walk through the slide step on the whiteboard: add calories[i], subtract calories[i - k]
• Show the boundary explicitly: the first window is the only one not built by sliding
• Mention LC 643 Maximum Average Subarray I as the most similar problem

Follow-up Questions#

• What if k can change between queries? (Hint: prefix sum, O(1) range query)
• What if the window must be at most k, not exactly k? (Hint: variable sliding window)
• What if you must return the day index of each scoring window? (Hint: track right pointer alongside sum)
• How would you handle this on a stream? (Hint: deque or rolling buffer)
• What is the relation to LC 1456 Maximum Number of Vowels? (Hint: same fixed window, replace sum with vowel count)

Key Takeaways#

• LeetCode 1176 Diet Plan Performance uses a fixed sliding window of size k
• Update the window sum in O(1) per step by adding the new element and subtracting the outgoing one
• Always evaluate the first window outside the slide loop to avoid double counting
• O(n) time and O(1) space, no prefix sum required
• Pattern extends to LC 643, LC 1456, and any fixed-size window question
• Google uses this as a phone screen warm-up before harder window problems
• Avoid recomputing the sum from scratch; that mistake costs O(n * k) and fails large inputs