Watch 10 video solutions for Diet Plan Performance, a easy level problem involving Array, Sliding Window. This walkthrough by Sergey Vinickiy has 3,535 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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]):
T < lower, they performed poorly on their diet and lose 1 point; T > upper, they performed well on their diet and gain 1 point;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[0] and calories[1] are less than lower so 2 points are lost. calories[3] and calories[4] 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[0] + calories[1] > upper so 1 point is gained.
Example 3:
Input: calories = [6,5,0,0], k = 2, lower = 1, upper = 5 Output: 0 Explanation: calories[0] + calories[1] > upper so 1 point is gained. lower <= calories[1] + calories[2] <= upper so no change in points. calories[2] + calories[3] < lower so 1 point is lost.
Constraints:
1 <= k <= calories.length <= 10^50 <= calories[i] <= 200000 <= lower <= upperProblem Overview: You are given an array calories where each value represents calories consumed on a day. For every consecutive block of k days, compute the total calories and compare it with thresholds lower and upper. If the sum is less than lower, the score decreases by 1. If it is greater than upper, the score increases by 1. Otherwise the score stays the same. The task is to return the final score after evaluating all windows of length k.
Approach 1: Prefix Sum (Time: O(n), Space: O(n))
This approach builds a prefix sum array so you can compute the sum of any subarray in constant time. First iterate through the array and store cumulative sums where prefix[i] represents the sum of the first i elements. Then iterate from index k to n, calculating each window sum using prefix[i] - prefix[i-k]. Compare that sum against lower and upper to update the score. The key idea is that prefix sums avoid recomputing the same ranges repeatedly, turning what would be an O(nk) brute force solution into O(n). This method is easy to reason about and useful when many arbitrary range queries are needed.
Approach 2: Sliding Window (Time: O(n), Space: O(1))
The optimal solution uses a fixed-size sliding window. Start by computing the sum of the first k elements. This represents the first window. For each next position, subtract the element leaving the window and add the element entering it. That single update keeps the running sum correct without recalculating the entire window. After each update, compare the window sum with lower and upper and adjust the score accordingly. Because each element enters and leaves the window exactly once, the algorithm runs in linear time while using constant extra memory. This pattern appears frequently in fixed-length subarray problems.
Recommended for interviews: The sliding window approach is what most interviewers expect. It demonstrates that you recognize the fixed window pattern and know how to maintain a running sum efficiently. Mentioning the prefix sum approach first shows that you understand range-sum optimization, but implementing the sliding window highlights stronger problem-solving instincts and memory efficiency.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum | O(n) | O(n) | Useful when multiple range sum queries are required or when prefix sums are already computed |
| Sliding Window | O(n) | O(1) | Best choice for fixed-size subarray problems where the window moves sequentially |