Leetcode solution 1176: Diet Plan Performance

Problem Statement?

• If?T < lower,they performed poorly on their diet and lose 1 point;?
• If?T > upper,they performed well on their diet and gain 1 point;
• Otherwise,they performed normally and there is no change in points.

Input: calories = [1,2,3,4,5],k = 1,lower = 3,upper = 3
Output: 0 Explanation: Since k = 1,we consider each element of the array separately and compare it to lower and upper. calories[0] and calories[1] are less than lower so 2 points are lost. calories[3] and calories[4] are greater than upper so 2 points are gained. 

Input: calories = [3,2],k = 2,lower = 0,upper = 1
Output: 1 Explanation: Since k = 2,we consider subarrays of length 2. calories[0] + calories[1] > upper so 1 point is gained. 

Input: calories = [6,5,0],lower = 1,upper = 5
Output: 0 Explanation: calories[0] + calories[1] > upper so 1 point is gained. lower <= calories[1] + calories[2] <= upper so no change in points. calories[2] + calories[3] < lower so 1 point is lost. 

• 1 <= k <= calories.length <= 10^5
• 0 <= calories[i] <= 20000
• 0 <= lower <= upper

Problem link

?

Video Tutorial

You can find the detailed video tutorial here

• Youtube
• B站

?

Thought Process

This is an easy problem but might be a bit hard to code it up correctly in one pass. We can use a sliding window to keep a rolling sum and compare it with upper and lower bound.

?

A few caveats in implementation:

• We can simplify using two pointers start and end by keeping an index i (start) and i - k (end)
• We can only have one loop instead of having two separate loops

?

Solutions

?

Sliding window

 1 public int dietPlanPerformance(int[] calories,int k,int lower,int upper) {
 2     if (calories == null || calories.length == 0) {
 3         return 0;
 4     }
 5 
 6     int rollingSum = 0;
 7     int performance = 0;
 8 
 9     for (int i = 0; i < calories.length; i++) {
10         // always adding element to the sliding window on the right
11         rollingSum += calories[i];
12         // initial value
13         if (i < k - 1) {
14             continue;
15         }
16 
17         // when to pop out element on the left
18         if (i >= k) {
19             rollingSum -= calories[i - k];
20         }
21         if (rollingSum > upper) {
22             performance++;
23         }
24         if (rollingSum < lower) {
25             performance--;
26         }
27     }
28 
29     return performance;
30 }

?

?

Time Complexity: O(N) visited the array once

Space Complexity: O(1) No extra space is needed

?

References

• None