1176. Diet Plan Performance
Problem Description
In this problem, a person is tracking their diet over a number of days, where each day they consume a certain number of calories. The caloric intake for each day is stored in an array where calories[i]
represents the calories consumed on the i
-th day. The person evaluates their diet every k
consecutive days, assessing whether they have gained or lost points based on their total caloric intake over those days. If the total caloric intake is less than a lower limit, the person loses a point; if it's more than an upper limit, they gain a point; otherwise, their score does not change. The task is to calculate the total number of points the person has after they have finished their diet, which can be a positive or negative number.
Intuition
The solution is based on a sliding window technique where the window size is k
. A sliding window is helpful in tracking a subset of data in a larger dataset, in this case, the caloric intake over k
consecutive days. The solution starts by calculating the initial sum of the first k
days. Then, as the window moves forward by one day at a time, instead of recalculating the sum from scratch, the solution simply subtracts the calories from the day that is no longer in the window and adds the calories from the new day. This ensures that the sum is maintained for the current window efficiently.
After each shift of the window, the new sum is checked against the lower and upper bounds to determine if a point should be lost, gained, or if the score remains the same. This check is encapsulated in a function called check(s)
, which returns -1, 1, or 0, respectively. By summing these up, we can find the total score after all days have been accounted for.
Learn more about Sliding Window patterns.
Solution Approach
The provided Python solution uses an efficient sliding window approach to solve the diet plan performance problem. The sliding window concept is applicable when it is required to calculate something among all contiguous subarrays of a certain length in an efficient manner.
Here is a breakdown of the implementation steps:
-
Initial Sum Calculation: The initial sum
s
of the calories for the firstk
days is calculated using the built-insum()
function on the slice of the firstk
elements of thecalories
list. -
Initial Points Calculation: The initial sum
s
is then passed to thecheck(s)
function, which comparess
with thelower
andupper
bounds. Depending on the comparison, the function returns -1, 1, or 0, representing losing a point, gaining a point, or no change in points, respectively. This initial points value is stored in theans
variable. -
Sliding the Window: The code enters a loop that will iterate starting from the
k
-th day to the last day. For each iteration, it adjusts the sum by subtracting the calorie count of the day that's exiting the window (calories[i - k]
) and adding the count of the new day entering the window (calories[i]
). This keeps the sums
up-to-date with the calorie count of the current window without having to re-calculate the sum from scratch. -
Update Points: After updating the sum for the new window position, the
check(s)
function is used again to determine if points should be gained or lost based on the new sum. The result is added to theans
variable, which accumulates the total points. -
Returning the Result: After all windows have been processed, the function returns
ans
, which contains the total points the dieter has after completing the diet.
This approach has a time complexity of O(n), where n is the number of days, and a space complexity of O(1), which makes it a very efficient solution.
The main tools used in the provided solution are the sliding window pattern and a helper function to calculate the point changes. The calories
list serves as the main data structure, with simple arithmetic used to manage the sum and points.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a simple example where a person is tracking their calories over 5 days:
1Calories = [1200, 1300, 1250, 1500, 1100], k = 2, lower = 2000, upper = 3000
The person evaluates their diet every 2 consecutive days and loses or gains points if their caloric intake is below 2000 or above 3000, respectively.
-
Initial Sum Calculation: Start by summing the first
k
days (2 days in this case), so sum the first and second day's calories:s = 1200 + 1300 = 2500
. -
Initial Points Calculation: Pass the initial sum
s
to thecheck(s)
function. Since2500
is between the lower and upper limits (2000 and 3000, respectively), they neither gain nor lose a point:ans = 0
. -
Sliding the Window: Now, for each day from the 3rd day to the 5th:
- Day 3 (New window: 1300, 1250): Adjust the sum to only include day 2 and 3 by subtracting day 1's calories and adding day 3's calories:
s = 2500 - 1200 + 1250 = 2550
. After that, check thes
value withcheck(s)
. Since 2550 is still between the lower and upper limits, no points are gained or lost, andans = 0
. - Day 4 (New window: 1250, 1500): Adjust the sum to include the calories from day 3 and 4:
s = 2550 - 1300 + 1500 = 2750
. Passs
tocheck(s)
. Since 2750 is also between the limits,ans
remains at0
. - Day 5 (New window: 1500, 1100): Adjust the sum for day 4 and 5:
s = 2750 - 1250 + 1100 = 2600
. Checks
withcheck(s)
. The sum is still between the limits, so the points stay the same,ans = 0
.
- Day 3 (New window: 1300, 1250): Adjust the sum to only include day 2 and 3 by subtracting day 1's calories and adding day 3's calories:
-
Update Points: At each step of the sliding window, we updated the
ans
based on thecheck(s)
function, which led to no change in this example. -
Returning the Result: The loop ends as there are no more windows to slide. The total points the dieter has after completing the diet are
ans = 0
.
The individual did not gain or lose any points during their diet according to the rules provided because their caloric intake stayed within the specified range for every assessment period.
Solution Implementation
1from typing import List
2
3class Solution:
4 def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:
5 # Helper function to evaluate the points for the given sum of calories
6 def evaluate_points(calories_sum):
7 # If the sum is less than the lower bound, return -1 point
8 if calories_sum < lower:
9 return -1
10 # If the sum is greater than the upper bound, return 1 point
11 elif calories_sum > upper:
12 return 1
13 # Otherwise, no points are awarded or deducted
14 else:
15 return 0
16
17 # Calculate the initial sum of the first 'k' elements
18 sliding_window_sum = sum(calories[:k])
19 # Initialize score with the points from initial sum
20 score = evaluate_points(sliding_window_sum)
21 # Length of the calories list
22 n = len(calories)
23
24 # Iterate over the remaining elements, updating the sum and score
25 for i in range(k, n):
26 # Update the sliding window sum by adding the current element and removing the oldest one
27 sliding_window_sum += calories[i] - calories[i - k]
28 # Update the score based on the updated sum
29 score += evaluate_points(sliding_window_sum)
30
31 # Return the total score after evaluating all sliding windows
32 return score
33
1class Solution {
2 public int dietPlanPerformance(int[] calories, int k, int lower, int upper) {
3
4 // Initialize the sum of the first 'k' elements.
5 int windowSum = 0;
6
7 // Calculate the sum of the first 'k' calories.
8 for (int i = 0; i < k; ++i) {
9 windowSum += calories[i];
10 }
11
12 // Initialize the performance points.
13 int points = 0;
14
15 // Check if the initial 'k' day period is below or above the threshold.
16 if (windowSum < lower) {
17 points--;
18 } else if (windowSum > upper) {
19 points++;
20 }
21
22 // Iterate through the array starting from the 'k'th day.
23 for (int i = k; i < calories.length; ++i) {
24 // Slide the window by 1: remove the first element and add the new one.
25 windowSum += calories[i] - calories[i - k];
26
27 // Adjust points based on the new sum.
28 if (windowSum < lower) {
29 points--;
30 } else if (windowSum > upper) {
31 points++;
32 }
33 }
34
35 // Return the calculated points.
36 return points;
37 }
38}
39
1#include <vector>
2#include <numeric>
3
4class Solution {
5public:
6 int dietPlanPerformance(std::vector<int>& calories, int k, int lower, int upper) {
7 int totalDays = calories.size();
8
9 // Calculate the total calories for the initial 'k' day period.
10 int currentCalories = std::accumulate(calories.begin(), calories.begin() + k, 0);
11
12 int performanceScore = 0; // Initialize the performance score.
13
14 // Update the performance score based on the initial 'k' day period.
15 if (currentCalories < lower) {
16 --performanceScore; // Decrease score when below lower limit.
17 } else if (currentCalories > upper) {
18 ++performanceScore; // Increase score when above upper limit.
19 }
20
21 // Slide the 'k' day window through the remaining days and update the performance score.
22 for (int i = k; i < totalDays; ++i) {
23 // Add the calorie of the new day and subtract the calorie of the day exiting the 'k' day window.
24 currentCalories += calories[i] - calories[i - k];
25
26 // Update the score based on the new 'k' day period's calorie count.
27 if (currentCalories < lower) {
28 --performanceScore;
29 } else if (currentCalories > upper) {
30 ++performanceScore;
31 }
32 }
33
34 return performanceScore; // Return the final performance score.
35 }
36};
37
1// Evaluates the diet plan performance by calculating points based on calorie intake over a sliding window.
2//
3// Parameters:
4// calories: An array representing daily calorie intake.
5// k: An integer representing the width of the sliding window of days.
6// lower: An integer representing the lower threshold of calories.
7// upper: An integer representing the upper threshold of calories.
8//
9// Returns:
10// The total points calculated by comparing the total calories in each window against the lower and upper thresholds.
11function dietPlanPerformance(calories: number[], k: number, lower: number, upper: number): number {
12 const totalDays = calories.length; // Total number of days represented in the calories array.
13 let windowSum = calories.slice(0, k).reduce((sum, current) => sum + current, 0); // Sum of first 'k' days.
14 let points = 0; // Initialize points to judge the performance.
15
16 // Award or deduct points based on the first 'k' days' total calories.
17 if (windowSum < lower) {
18 points--;
19 } else if (windowSum > upper) {
20 points++;
21 }
22
23 // Slide the window one day at a time, updating the sum and points accordingly.
24 for (let i = k; i < totalDays; ++i) {
25 windowSum += calories[i] - calories[i - k]; // Update the window sum by adding the new day's calories and subtracting the first day's calories from the previous window.
26
27 // Award or deduct points based on the current window's calories.
28 if (windowSum < lower) {
29 points--;
30 } else if (windowSum > upper) {
31 points++;
32 }
33 }
34
35 return points; // Return the calculated points.
36}
37
Time and Space Complexity
The provided code defines a function dietPlanPerformance
that calculates a diet plan performance score based on calories intake over a sliding window of size k
, and compares each window's sum with given lower
and upper
bounds.
Time Complexity
The time complexity of the code is O(n)
, where n
is the total number of days (length of the calories
array).
Let's break down the operation:
- Summation of the first
k
elements is done inO(k)
time. - Following this initialization, the function iterates over the remaining elements, from
k
ton-1
. For each iteration, it takes constant time to update the sums
(due to the subtraction of the oldest calorie value and the addition of the new calorie value) and to evaluate the check function. The loop, therefore, runs(n-k)
times. - Since
k
is a constant with respect ton
, the time taken for initial summation is negligible for largen
. Thus, the dominant term is(n-k)
, which simplifies toO(n)
for largen
.
1O(k) + O(n-k) = O(n)
Space Complexity
The space complexity of the code is O(1)
.
Here's why:
- The extra space used by the program is constant, as it only requires a fixed number of single-value variables (
s
,n
, andans
) regardless of the input size. - No additional data structures that scale with the input size are used; the input list itself is not modified.
- The check function is defined within the method and does not consume extra space that depends on the input size.
1O(1)
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a good use case for backtracking?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.