Solution: Diet Plan Performance

Let’s solve the Diet Plan Performance problem using the sliding window pattern.

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 than lower, the dieter performs poorly and loses 1 point.

  • If T is greater than upper, the dieter performs better and gains 1 point.

  • If T is between lower and upper (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

  • 1k1 \leq k \leq calories.length 105\leq 10^5

  • 00 \leq calories[i] 20000\leq 20000

  • 00 \leq lower upper\leq \text{upper}

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 against lower and upper. If it’s less than lower, points decrease by 11. If it’s greater than the upper, points increase by 11. 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 11 if the sum is less than the lower.

    • Add 11 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.