1176. Diet Plan Performance
Model: qwen2.5-coder:14b
Topics: Array,Sliding Window
FAANG asked: 1
Acceptance rate: 53.8%
Problem Breakdown
The problem involves calculating the diet performance points for a dieter based on their daily calorie intake over a period of days. The dieter earns or loses points based on whether their total calorie consumption over any consecutive k-day window falls below a specified lower limit, exceeds an upper limit, or stays within both limits.
Inputs:
calories: An array of integers where each element represents the calories consumed on a given day.k: An integer representing the number of consecutive days to consider for calculating the total calorie intake.lower: An integer representing the lower bound for daily calorie consumption.upper: An integer representing the upper bound for daily calorie consumption.
Outputs:
- An integer representing the total points earned or lost by the dieter after considering all possible
k-day windows.
Implicit Constraints and Edge Cases:
- The length of the
caloriesarray is between 1 and (10^5). - Each element in
caloriesis between 0 and 20,000. loweris between 0 and the maximum possible total calories for anyk-day window.- The input array can be empty or contain only one element.
Intuition
A brute-force approach would involve iterating over all possible starting points of the k-day windows, calculating the sum of calories for each window, and then checking if it falls below, above, or within the specified limits. This approach has a time complexity of (O(n \times k)), which is inefficient given the constraints.
The key insight to optimize this solution is to use a sliding window technique. By maintaining a running total of the calories for the current k-day window and updating it as we slide the window one day at a time, we can achieve a linear time complexity of (O(n)).
Approach
-
Initialize Variables:
total_points: To keep track of the total points earned or lost.current_sum: To maintain the sum of calories for the currentk-day window.
-
Calculate Initial Window Sum:
- Compute the sum of the first
kdays and updatecurrent_sum.
- Compute the sum of the first
-
Sliding Window Calculation:
- Iterate through the array starting from the
k-th day. - For each new day, add its calories to
current_sumand subtract the calories that are no longer in the window (i.e., the calorie count fromi-kdays ago). - After updating
current_sum, check if it is less thanlower, greater thanupper, or within both limits, and updatetotal_pointsaccordingly.
- Iterate through the array starting from the
-
Return Total Points:
- After processing all possible windows, return the accumulated
total_points.
- After processing all possible windows, return the accumulated
Complexity Analysis
- Time Complexity: (O(n)), where (n) is the length of the
caloriesarray. This is because we only iterate through the array once to calculate the initial window sum and then slide the window across the array. - Space Complexity: (O(1)), as we use a constant amount of extra space regardless of the input size.
Solution
def dietPlanPerformance(calories, k, lower, upper):
total_points = 0
current_sum = sum(calories[:k])
if current_sum < lower:
total_points -= 1
elif current_sum > upper:
total_points += 1
for i in range(k, len(calories)):
current_sum += calories[i] - calories[i - k]
if current_sum < lower:
total_points -= 1
elif current_sum > upper:
total_points += 1
return total_points
Edge Cases Handled
- Single Day (
k = 1): The algorithm correctly handles the case where each day is considered individually. - Empty Input Array: Although not explicitly mentioned, if the input array is empty, the function will return 0 as there are no days to evaluate.
- All Calories Below Lower Limit: If all
k-day windows have a total calorie count belowlower, the function will correctly accumulate negative points. - All Calories Above Upper Limit: Similarly, if all
k-day windows have a total calorie count aboveupper, the function will correctly accumulate positive points.