Leet Code - Sliding Window - Maximum Average Subarray I

---

🔶 Problem: Maximum Average Subarray I

📝 Description:

Given an integer array nums and an integer k, find the contiguous subarray of length k that has the maximum average value, and return this value.

---

📥 Example:

Input: nums = [1,12,-5,-6,50,3], k = 4  
Output: 12.75  
Explanation: Maximum average subarray is [12,-5,-6,50] with average = (12−5−6+50)/4 = 12.75

---

🚫 Brute-force Approach (Bad Way)

❌ Time Complexity: O(n * k)

We calculate the average of every subarray of size k.

double findMaxAverage(vector<int>& nums, int k) {
    double maxAvg = INT_MIN;
    for (int i = 0; i <= nums.size() - k; i++) {
        double sum = 0;
        for (int j = i; j < i + k; j++) {
            sum += nums[j];
        }
        maxAvg = max(maxAvg, sum / k);
    }
    return maxAvg;
}

🔁 Outer loop runs for:
i = 0 to nums.size() - k = 6 - 4 = 2
So it runs for i = 0, 1, 2.
🧠 Iteration-by-iteration Breakdown:
▶️ i = 0
j = 0 to 3
sum = nums[0] + nums[1] + nums[2] + nums[3]
    = 1 + 12 + (-5) + (-6) = 2
avg = 2 / 4 = 0.5
maxAvg = max(INT_MIN, 0.5) = 0.5

▶️ i = 1
j = 1 to 4
sum = 12 + (-5) + (-6) + 50 = 51
avg = 51 / 4 = 12.75
maxAvg = max(0.5, 12.75) = 12.75
▶️ i = 2
j = 2 to 5
sum = -5 + (-6) + 50 + 3 = 42
avg = 42 / 4 = 10.5
maxAvg = max(12.75, 10.5) = 12.75

✅ Final Result:
return maxAvg = 12.75
📋 Summary Table:




i
Subarray
Sum
Average
maxAvg Update




0
[1, 12, -5, -6]
2
0.5
0.5


1
[12, -5, -6, 50]
51
12.75
12.75 (updated)


2
[-5, -6, 50, 3]
42
10.5
12.75 (unchanged)


❌ Why it's bad:

• You recalculate the same numbers multiple times.

• Too slow for large arrays.

---

✅ Optimal Sliding Window Approach (Best Way)

⏱ Time: O(n) — each element added/removed once

💾 Space: O(1) — no extra data structure needed

double findMaxAverage(vector<int>& nums, int k) {
    int windowSum = 0;
    
    // Sum of first window
    for (int i = 0; i < k; i++) {
        windowSum = windowSum + nums[i];
    }

    int maxSum = windowSum;

    for (int i = k; i < nums.size(); i++) {
        windowSum = windowSum + nums[i] - nums[i - k]; // Slide the window
        maxSum = max(maxSum, windowSum);
    }

    return static_cast<double>(maxSum) / k;
}

---

🧠 Step-by-step (for input [1,12,-5,-6,50,3], k = 4):

Initialization:

• windowSum = 1 + 12 + (-5) + (-6) = 2

• maxSum = 2

Iteration:

1. i = 4: Add 50, remove 1
   → windowSum = 2 + 50 - 1 = 51
   → maxSum = 51

2. i = 5: Add 3, remove 12
   → windowSum = 51 + 3 - 12 = 42
   → maxSum = 51

Final:

• Max sum = 51

• Max average = 51 / 4 = 12.75

---

🔍 With/Without Data Structures?

• ❌ No need for a queue, deque, map, etc.

• ✔️ You just track the running window sum → simplest and fastest.

---

✅ Summary

Approach	Time	Space	Notes
Brute-force	O(n * k)	O(1)	Repeats work — not optimal
✅ Sliding window	O(n)	O(1)	Best way — clean and fast

---