LeetCode 1176 - Diet Plan Performance

LeetCode Problem 1176

Difficulty: 🟢 Easy
Topics: Array, Sliding Window

Solution

Problem Understanding

The problem is asking us to simulate a dieter’s performance over a sequence of days based on their calorie consumption. The input is an array calories where calories[i] represents the number of calories consumed on day i. We are also given three integers: k, lower, and upper. For every consecutive sequence of k days, we calculate the total calories T. The rules for scoring are simple: if T < lower, the dieter loses 1 point; if T > upper, they gain 1 point; otherwise, there is no change in points. The goal is to calculate the total points after evaluating all possible consecutive sequences of length k.

The constraints indicate that k will always be at least 1 and at most the length of the calories array, which itself can be up to 10^5. Each calorie count is non-negative and bounded by 20,000. The lower and upper thresholds are also non-negative and lower will not exceed upper. This suggests that the solution must efficiently handle large arrays, and brute-force approaches that recompute sums for all subarrays could be too slow. Edge cases to consider include very small arrays, k equal to the array length, sequences where all elements are equal, and scenarios where all subarrays are exactly at the lower or upper thresholds.

Approaches

The brute-force approach involves iterating through every possible subarray of length k and computing its sum. Once the sum is calculated, it is compared to lower and upper to adjust the points accordingly. While this approach is straightforward and correct, it is inefficient because computing the sum of a length-k subarray for each starting index i requires O(k) time. With n elements, this results in O(n*k) time complexity, which is too slow for n up to 100,000.

The key observation for optimization is that we can maintain a running sum of length k using a sliding window. Instead of recomputing the sum for each subarray from scratch, we initialize the sum for the first k elements and then slide the window one element at a time: subtract the element leaving the window and add the element entering the window. This allows each sum calculation to be done in O(1) time, reducing the overall complexity to O(n). This technique is applicable because consecutive subarrays overlap significantly, so reusing previous computations is efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n*k)	O(1)	Calculate sum of each subarray independently
Optimal	O(n)	O(1)	Sliding window approach for consecutive sums

Algorithm Walkthrough

1. Initialize two variables: points to 0 to keep track of the score, and window_sum to 0 to store the sum of the current window of size k.
2. Compute the sum of the first k elements and store it in window_sum. Compare window_sum to lower and upper and adjust points according to the rules.
3. Slide the window through the array starting from index k to the end. For each new element entering the window, add it to window_sum and subtract the element leaving the window (which is calories[i-k]).
4. After updating window_sum, compare it to lower and upper. If window_sum < lower, decrement points by 1. If window_sum > upper, increment points by 1. Otherwise, do nothing.
5. Continue until the window reaches the end of the array.
6. Return the final points value.

Why it works: At each step, the window sum represents exactly the sum of k consecutive days. The sliding window ensures that every possible subarray of length k is evaluated exactly once. The score updates according to the problem rules, so the final points value is guaranteed to be correct.

Python Solution

from typing import List

class Solution:
    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:
        points = 0
        window_sum = sum(calories[:k])
        
        if window_sum < lower:
            points -= 1
        elif window_sum > upper:
            points += 1
        
        for i in range(k, len(calories)):
            window_sum += calories[i] - calories[i - k]
            if window_sum < lower:
                points -= 1
            elif window_sum > upper:
                points += 1
        
        return points

The implementation initializes the points counter and calculates the initial sum for the first k days. It then slides the window through the array, updating the sum in O(1) time for each new position. The score is adjusted immediately after each window update, ensuring the final score accurately reflects all subarrays of length k.

Go Solution

func dietPlanPerformance(calories []int, k int, lower int, upper int) int {
    points := 0
    windowSum := 0
    
    for i := 0; i < k; i++ {
        windowSum += calories[i]
    }
    
    if windowSum < lower {
        points--
    } else if windowSum > upper {
        points++
    }
    
    for i := k; i < len(calories); i++ {
        windowSum += calories[i] - calories[i-k]
        if windowSum < lower {
            points--
        } else if windowSum > upper {
            points++
        }
    }
    
    return points
}

The Go implementation mirrors the Python version. Go handles slices similarly to Python lists, so the sliding window logic is identical. There are no concerns with nil slices since the problem guarantees k >= 1. Integer overflow is not a concern due to the constraints on calories[i] and k.

Worked Examples

Example 1: calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3

i	window_sum	points update	points
0	1	< lower	-1
1	2	< lower	-2
2	3	in range	-2
3	4	> upper	-1
4	5	> upper	0

Final points: 0

Example 2: calories = [3,2], k = 2, lower = 0, upper = 1

i	window_sum	points update	points
0	5	> upper	1

Final points: 1

Example 3: calories = [6,5,0,0], k = 2, lower = 1, upper = 5

i	window_sum	points update	points
0	11	> upper	1
1	5	in range	1
2	0	< lower	0

Final points: 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Sliding window sums are updated in O(1) per step for n elements
Space	O(1)	Only a few integer variables are used, no extra data structures

The algorithm is efficient because it avoids recomputing sums for overlapping subarrays, leveraging the overlap to achieve linear time.

Test Cases

# Example tests
assert Solution().dietPlanPerformance([1,2,3,4,5], 1, 3, 3) == 0  # mixed below and above
assert Solution().dietPlanPerformance([3,2], 2, 0, 1) == 1         # total > upper
assert Solution().dietPlanPerformance([6,5,0,0], 2, 1, 5) == 0    # mixed cases

# Edge cases
assert Solution().dietPlanPerformance([0], 1, 0, 0) == 0           # single element exactly at threshold
assert Solution().dietPlanPerformance([10**4]*10**5, 10**5, 50000, 2000000) == 1  # large input
assert Solution().dietPlanPerformance([1,1,1,1], 4, 5, 5) == -1   # sum < lower
assert Solution().dietPlanPerformance([5,5,5,5], 4, 5, 5) == 0    # sum == threshold
assert Solution().dietPlanPerformance([10,10,10,10], 4, 5, 20) == 1 # sum > upper

Test	Why
[1,2,3,4,5], k=1	Tests single-day windows with mixed below/above
[3,2], k=2	Tests multi-day window where sum exceeds upper
[6,5,0,0], k=2	Mixed cases including exact lower and upper checks