Is Diet Plan Performance easy or hard?

Diet Plan Performance is categorized as an Easy problem on LeetCode with an acceptance rate around 55%. It mainly tests understanding of the sliding window technique and efficient subarray sum calculations.

Diet Plan Performance Python/Java solution

Implement the sliding window by first computing the sum of the first k elements. Iterate from index k to the end of the array, update the running sum by removing the leftmost element and adding the new one, then adjust the score based on lower and upper thresholds. The same logic works in Python, Java, C++, Go, and TypeScript.

How to solve Diet Plan Performance in O(n)?

Compute the sum of the first k elements to initialize the window. Then slide the window across the array by subtracting calories[i-k] and adding calories[i] at each step. Compare each window sum to lower and upper thresholds and update the score accordingly. This single pass guarantees O(n) time.

What is the best approach for Diet Plan Performance?

The sliding window approach is the most efficient and commonly expected solution. Maintain the sum of a window of size k and update it by subtracting the outgoing element and adding the incoming one. This keeps the computation O(n) time and O(1) space while scanning the array once.

Is Diet Plan Performance asked at Google/Amazon/Meta?

This problem follows a classic sliding window pattern frequently used in technical interviews at companies like Amazon and Google. While the exact problem may vary, fixed-size window sum problems are a common interview theme.

What data structure is used in Diet Plan Performance?

The solution primarily uses arrays and a running integer sum. The sliding window technique operates directly on the array while maintaining a constant-size window, making additional data structures unnecessary.

What is the time complexity of Diet Plan Performance?

The optimal solution runs in O(n) time where n is the number of days in the calories array. Each element is processed at most twice (once entering the window and once leaving). Space complexity is O(1) for the sliding window approach or O(n) if a prefix sum array is used.

Description Hints 1 Solution Video 4:24

1176. Diet Plan Performance

Easy55.9% acceptance1 companyPremium elsewhere, free here

A dieter consumes calories[i] calories on the i-th day.

Given an integer k, for every consecutive sequence of k days (calories[i], calories[i+1], ..., calories[i+k-1] for all 0 <= i <= n-k), they look at T, the total calories consumed during that sequence of k days (calories[i] + calories[i+1] + ... + calories[i+k-1]):

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.

Initially, the dieter has zero points. Return the total number of points the dieter has after dieting for calories.length days.

Note that the total points can be negative.

Example 1:

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.

Example 2:

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.

Example 3:

Input: calories = [6,5,0,0], k = 2, 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.

Constraints:

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

Asked at 1 company

Amazon

Topics

Array Sliding Window

Hints open one at a time

Hint 1

Use sliding window technique (aka two pointers).

4:24

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,2,3,4,5]
1
3
3

Input

[3,2]
2
0
1

Input

[6,5,0,0]
2
1
5

Your code is saved on this device.Solution