Given an array calories, where calories[i] represents the calories consumed on day i, calculate the total score for a diet plan.
Consider every group of k consecutive days, moving the group forward one day at a time. For each group, calculate its total calories T.
Start with 0 points and apply these rules once per group:
If
T < lower, subtract1point.If
T > upper, add1point.If
lower ≤ T ≤ upper, leave the score unchanged.
Return the final score after evaluating all groups. The score can be negative.
Example 1
Input: calories = [3, 2, 6, 5, 7], k = 2, lower = 6, upper = 10
Output: 1
Explanation: The window totals 5, 8, 11, 12 contribute -1, 0, +1, +1, giving a final score of 1.
Example 2
Input: calories = [1, 4, 2, 1], k = 2, lower = 6, upper = 8
Output: -2
Explanation: The window totals 5, 6, 3 contribute -1, 0, -1, giving a final score of -2.
Approach
A group of k consecutive days is called a window. Each window is evaluated using its total calories: a total below lower loses one point, a total above upper gains one point, and a total within the limits leaves the score unchanged. These changes are added together to obtain the final score.
Neighbouring windows share k - 1 days. Moving forward by one day removes only the oldest day and includes only one new day. Since the shared days are already included in the current total, the next total can be found by subtracting the outgoing day’s calories and adding the incoming day’s calories.
This is the sliding-window approach. Calculate and score the first window, then update its total as it moves forward. Score each new window exactly once, keeping the current calorie total separate from the accumulated points. After all windows have been evaluated, the accumulated points give the answer.
Algorithm
Calculate the total calories for the first
kdays.Score this window: subtract
1if its total is belowlower, add1if it is aboveupper, and make no change otherwise.Move the window forward by one day, subtracting the outgoing day’s calories and adding the incoming day’s calories.
Score the updated window and repeat until every complete window has been evaluated.
Return the accumulated points.
Dry Run
Diet plan performance
Solution
#include<bits/stdc++.h>using namespace std;class Solution {public: // Returns the total score across all consecutive groups of k days. int dietPlanPerformance(const vector<int>& calories, int k, int lower, int upper) { int points = 0; long long windowSum = 0; // Calculate the total for the first complete window. for (int i = 0; i < k; i++) { windowSum += calories[i]; } // Score the first window; equality with either limit changes nothing. if (windowSum < lower) { points--; } else if (windowSum > upper) { points++; } for (int right = k; right < calories.size(); right++) { // Remove the outgoing day and include the incoming day. windowSum -= calories[right - k]; windowSum += calories[right]; // Score this new window exactly once. if (windowSum < lower) { points--; } else if (windowSum > upper) { points++; } } return points; }};// Driver codeint main() { vector<int> calories = {3, 2, 6, 5, 7}; int k = 2; int lower = 6; int upper = 10; // Create an instance of class Solution. Solution sol; cout << sol.dietPlanPerformance(calories, k, lower, upper) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(N), where N is the number of days. Calculating the first window takes O(K) time, and each of the remaining N - K windows requires a constant-time update.
Space Complexity: O(1) auxiliary space because only the current window’s sum, accumulated points, and loop positions are stored.
Interview follow-up Questions
When k = 1, each day is scored separately. When k equals the array’s length, there is only one window, so the final score can only be -1, 0, or 1.
Be the first to add a comment.