Domain 1EasyCORE

Diet Plan Performance

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.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Sliding Window

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 calories array is between 1 and (10^5).
  • Each element in calories is between 0 and 20,000.
  • lower is between 0 and the maximum possible total calories for any k-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

  1. Initialize Variables:

    • total_points: To keep track of the total points earned or lost.
    • current_sum: To maintain the sum of calories for the current k-day window.
  2. Calculate Initial Window Sum:

    • Compute the sum of the first k days and update current_sum.
  3. Sliding Window Calculation:

    • Iterate through the array starting from the k-th day.
    • For each new day, add its calories to current_sum and subtract the calories that are no longer in the window (i.e., the calorie count from i-k days ago).
    • After updating current_sum, check if it is less than lower, greater than upper, or within both limits, and update total_points accordingly.
  4. Return Total Points:

    • After processing all possible windows, return the accumulated total_points.

Complexity Analysis

  • Time Complexity: (O(n)), where (n) is the length of the calories array. 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 below lower, the function will correctly accumulate negative points.
  • All Calories Above Upper Limit: Similarly, if all k-day windows have a total calorie count above upper, the function will correctly accumulate positive points.