1176. Diet Plan Performance Solution

The problem

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

Approach overview

Problem Overview: You are given an array calories where each value represents calories consumed on a day. For every consecutive block of k days, compute the total calories and compare it with thresholds lower and upper. If the sum is less than lower, the score decreases by 1. If it is greater than upper, the score increases by 1. Otherwise the score stays the same. The task is to return the final score after evaluating all windows of length k.

Approach 1: Prefix Sum (Time: O(n), Space: O(n))

This approach builds a prefix sum array so you can compute the sum of any subarray in constant time. First iterate through the array and store cumulative sums where prefix[i] represents the sum of the first i elements. Then iterate from index k to n, calculating each window sum using prefix[i] - prefix[i-k]. Compare that sum against lower and upper to update the score. The key idea is that prefix sums avoid recomputing the same ranges repeatedly, turning what would be an O(nk) brute force solution into O(n). This method is easy to reason about and useful when many arbitrary range queries are needed.

Approach 2: Sliding Window (Time: O(n), Space: O(1))

The optimal solution uses a fixed-size sliding window. Start by computing the sum of the first k elements. This represents the first window. For each next position, subtract the element leaving the window and add the element entering it. That single update keeps the running sum correct without recalculating the entire window. After each update, compare the window sum with lower and upper and adjust the score accordingly. Because each element enters and leaves the window exactly once, the algorithm runs in linear time while using constant extra memory. This pattern appears frequently in fixed-length subarray problems.

Recommended for interviews: The sliding window approach is what most interviewers expect. It demonstrates that you recognize the fixed window pattern and know how to maintain a running sum efficiently. Mentioning the prefix sum approach first shows that you understand range-sum optimization, but implementing the sliding window highlights stronger problem-solving instincts and memory efficiency.

Approach 1: Prefix Sum

First, we preprocess a prefix sum array s of length n+1, where s[i] represents the total calories of the first i days.

Then we traverse the prefix sum array s. For each position i, we calculate s[i+k]-s[i], which is the total calories for the consecutive k days starting from the ith day. According to the problem description, for each s[i+k]-s[i], we judge its value with lower and upper, and update the answer accordingly.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the calories array.

Python

class Solution:
    def dietPlanPerformance(
        self, calories: List[int], k: int, lower: int, upper: int
    ) -> int:
        s = list(accumulate(calories, initial=0))
        ans, n = 0, len(calories)
        for i in range(n - k + 1):
            t = s[i + k] - s[i]
            if t < lower:
                ans -= 1
            elif t > upper:
                ans += 1
        return ans

Java

class Solution {
    public int dietPlanPerformance(int[] calories, int k, int lower, int upper) {
        int n = calories.length;
        int[] s = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + calories[i];
        }
        int ans = 0;
        for (int i = 0; i < n - k + 1; ++i) {
            int t = s[i + k] - s[i];
            if (t < lower) {
                --ans;
            } else if (t > upper) {
                ++ans;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int dietPlanPerformance(vector<int>& calories, int k, int lower, int upper) {
        int n = calories.size();
        int s[n + 1];
        s[0] = 0;
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + calories[i];
        }
        int ans = 0;
        for (int i = 0; i < n - k + 1; ++i) {
            int t = s[i + k] - s[i];
            if (t < lower) {
                --ans;
            } else if (t > upper) {
                ++ans;
            }
        }
        return ans;
    }
};

TypeScript

function dietPlanPerformance(calories: number[], k: number, lower: number, upper: number): number {
    const n = calories.length;
    const s: number[] = new Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        s[i + 1] = s[i] + calories[i];
    }
    let ans = 0;
    for (let i = 0; i < n - k + 1; ++i) {
        const t = s[i + k] - s[i];
        if (t < lower) {
            --ans;
        } else if (t > upper) {
            ++ans;
        }
    }
    return ans;
}

func dietPlanPerformance(calories []int, k int, lower int, upper int) (ans int) {
	n := len(calories)
	s := make([]int, n+1)
	for i, x := range calories {
		s[i+1] = s[i] + x
	}
	for i := 0; i < n-k+1; i++ {
		t := s[i+k] - s[i]
		if t < lower {
			ans--
		} else if t > upper {
			ans++
		}
	}
	return
}

Try this approach in the editor

Approach 2: Sliding Window

We maintain a sliding window of length k, and the sum of the elements in the window is denoted as s. If s \lt lower, the score decreases by 1; if s > upper, the score increases by 1.

The time complexity is O(n), where n is the length of the calories array. The space complexity is O(1).

Python

class Solution:
    def dietPlanPerformance(
        self, calories: List[int], k: int, lower: int, upper: int
    ) -> int:
        def check(s):
            if s < lower:
                return -1
            if s > upper:
                return 1
            return 0

        s, n = sum(calories[:k]), len(calories)
        ans = check(s)
        for i in range(k, n):
            s += calories[i] - calories[i - k]
            ans += check(s)
        return ans

Java

class Solution {
    public int dietPlanPerformance(int[] calories, int k, int lower, int upper) {
        int s = 0, n = calories.length;
        for (int i = 0; i < k; ++i) {
            s += calories[i];
        }
        int ans = 0;
        if (s < lower) {
            --ans;
        } else if (s > upper) {
            ++ans;
        }
        for (int i = k; i < n; ++i) {
            s += calories[i] - calories[i - k];
            if (s < lower) {
                --ans;
            } else if (s > upper) {
                ++ans;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int dietPlanPerformance(vector<int>& calories, int k, int lower, int upper) {
        int n = calories.size();
        int s = accumulate(calories.begin(), calories.begin() + k, 0);
        int ans = 0;
        if (s < lower) {
            --ans;
        } else if (s > upper) {
            ++ans;
        }
        for (int i = k; i < n; ++i) {
            s += calories[i] - calories[i - k];
            if (s < lower) {
                --ans;
            } else if (s > upper) {
                ++ans;
            }
        }
        return ans;
    }
};

TypeScript

function dietPlanPerformance(calories: number[], k: number, lower: number, upper: number): number {
    const n = calories.length;
    let s = calories.slice(0, k).reduce((a, b) => a + b);
    let ans = 0;
    if (s < lower) {
        --ans;
    } else if (s > upper) {
        ++ans;
    }
    for (let i = k; i < n; ++i) {
        s += calories[i] - calories[i - k];
        if (s < lower) {
            --ans;
        } else if (s > upper) {
            ++ans;
        }
    }
    return ans;
}

func dietPlanPerformance(calories []int, k int, lower int, upper int) (ans int) {
	n := len(calories)
	s := 0
	for _, x := range calories[:k] {
		s += x
	}
	if s < lower {
		ans--
	} else if s > upper {
		ans++
	}
	for i := k; i < n; i++ {
		s += calories[i] - calories[i-k]
		if s < lower {
			ans--
		} else if s > upper {
			ans++
		}
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Prefix Sum	–
Sliding Window	–

Complexity analysis

Approach	Time	Space	When to Use
Prefix Sum	O(n)	O(n)	Useful when multiple range sum queries are required or when prefix sums are already computed
Sliding Window	O(n)	O(1)	Best choice for fixed-size subarray problems where the window moves sequentially

Frequently asked questions

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.

Diet Plan Performance solution and explanation

The problem

Approach overview

Approach 1: Prefix Sum

Approach 2: Sliding Window

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Diet Plan Performance solution and explanation

The problem

Approach overview

Approach 1: Prefix Sum

Approach 2: Sliding Window

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems