Solution: Diet Plan Performance
Let’s solve the Diet Plan Performance problem using the sliding window pattern.
We'll cover the following
Statement
A dieter consumes calories[i]
calories on the i-th
day.
Given an integer k
, the dieter reviews their calorie intake over every sequence of k
consecutive days (from calories[i]
to calories[i+k-1]
for all 0 <= i <= n-k
). For each sequence, they calculate T
, the total calories consumed over those k
days:
If
T
is less thanlower
, the dieter performs poorly and loses 1 point.If
T
is greater thanupper
, the dieter performs better and gains 1 point.If
T
is betweenlower
andupper
(inclusive), the dieter’s performance is normal, and their points remain the same.
The dieter starts with zero points. Return the total points after the dieter follows this routine for all calories.length
days. The total points can be negative.
Constraints
calories.length
calories[i]
lower
Solution
This problem aims to track the dieter’s performance over every sequence of k
consecutive days based on their calorie intake. A sliding window approach is ideal because it allows us to calculate the sum of k
consecutive days without recalculating the sum from scratch for each new sequence. In the sliding window technique, we maintain a running sum of the current window of k
days. As we move the window one day forward, we adjust the sum by subtracting the day’s calorie count, sliding out of the window, and adding the calorie count of the new day entering the window. This approach ensures that we update the sum and assess the dieter’s performance across all possible sequences of k
days.
Here’s the step-by-step explanation of the solution:
We initialize the points to zero and calculate the sum of the first
k
days to form the initial window.The sum of the initial
k
days is checked againstlower
andupper
. If it’s less thanlower
, points decrease by. If it’s greater than the upper
, points increase by. Otherwise, the points remain the same. We iterate over the rest of the array starting from index
k
, updating the current sum by removing the element that slides out of the window and adding the new element that comes into the window.For each updated sum, we adjust the points based on the performance conditions:
Subtract
if the sum is less than the lower
.Add
if the sum is greater than the upper
.No change if the sum is within
[lower, upper]
.
After evaluating all possible windows of
k
days, we return the accumulated points.
Let’s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.