Diet Plan Performance - Solution & Explanation
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[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 <= upper
Approach Overview
Problem 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 1: Prefix Sum
First, we preprocess a prefix sum array s of length n+1, where s[i] represents the total calories of the first i days.
Then we traverse the prefix sum array s. For each position i, we calculate s[i+k]-s[i], which is the total calories for the consecutive k days starting from the ith day. According to the problem description, for each s[i+k]-s[i], we judge its value with lower and upper, and update the answer accordingly.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the calories array.
Code
Python
Java
C++
Go
TypeScript
Approach 2: Sliding Window
We maintain a sliding window of length k, and the sum of the elements in the window is denoted as s. If s \lt lower, the score decreases by 1; if s > upper, the score increases by 1.
The time complexity is O(n), where n is the length of the calories array. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Prefix Sum | — |
| Sliding Window | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Собеседование в IT | LeetCode | 1176. Diet Plan Performance • Sergey Vinickiy • 3,535 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Diet Plan Performance easy or hard?
Diet Plan Performance Python/Java solution
How to solve Diet Plan Performance in O(n)?
What is the best approach for Diet Plan Performance?
Is Diet Plan Performance asked at Google/Amazon/Meta?
What data structure is used in Diet Plan Performance?
What is the time complexity of Diet Plan Performance?
Ready to solve this problem?
Practice Diet Plan Performance with our built-in code editor and test cases.
Practice on FleetCode