Sliding Window — Diet Plan Performance
↗ LeetCode: Diet Plan Performance · Easy · pattern chapter →
Fixed window of size k over calories. For each window: +1 if sum > upper; −1 if sum < lower; 0 otherwise. Return total score.
Example 1 — calories=[1,2,3,4,5], k=1, lower=3, upper=3 → 0Example 2 — calories=[3,2], k=2, lower=0, upper=1 → 1Example 3 — calories=[6,5,0,0], k=2, lower=1, upper=5 → 0
Constraints — 1 ≤ n ≤ 10⁵; 1 ≤ k ≤ n. Naive per-window sum is O(nk) — at n=k=10⁵ that's 10¹⁰ ops (~5 minutes). Sliding-window is O(n).
Interview timer00:00
Approach 1 — Brute force per-window sum
Intuition. For each window start i, sum k items. Score.
int dietPlanPerformanceBrute(int[] cal, int k, int lower, int upper) {
int score = 0;
for (int i = 0; i + k <= cal.length; i++) {
int sum = 0;
for (int j = i; j < i + k; j++) sum += cal[j];
if (sum > upper) score++;
else if (sum < lower) score--;
}
return score;
}Complexity — Time O(nk); Space O(1). For n=k=10⁵: 10¹⁰ ops = TLE. In an interview say "add-in, drop-out sliding sum → O(n)."
Approach 2 — Fixed-window running sum (canonical)
Insight. Consecutive windows share k-1 items. Pre-sum the first k; then slide by adding the incoming right and subtracting the outgoing left — one add, one subtract per step.
int dietPlanPerformance(int[] cal, int k, int lower, int upper) {
int sum = 0;
for (int i = 0; i < k; i++) sum += cal[i];
int score = 0;
if (sum > upper) score++;
else if (sum < lower) score--;
for (int i = k; i < cal.length; i++) {
sum += cal[i] - cal[i - k];
if (sum > upper) score++;
else if (sum < lower) score--;
}
return score;
}Complexity — Time O(n); Space O(1). Say aloud in an interview: "fixed-window sliding is the simplest form of the pattern — every 'per-window aggregate' problem starts here."
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Per-window sum brute | O(nk) | O(1) | Reference; TLE at 10⁵ |
| Fixed window slide | O(n) | O(1) | Canonical |
When to use which
- Fixed window size + accumulator → this template.
- Variable window → shrink/extend on validity.
- Return per-window score list → append instead of accumulating.