Maximum Average Subarray I – Sliding Window & Prefix Sum Optimization (LeetCode Explained)

Maximum Average Subarray I – Sliding Window Optimization Explained

While solving LeetCode – Maximum Average Subarray I, I initially implemented a straightforward sliding window solution. Although the logic was correct, it resulted in a Time Limit Exceeded (TLE) error. This problem became a good learning example of why optimization matters and how prefix sums can drastically improve performance.

---

Initial Approach (Naive Sliding Window)

My first solution calculated the average of every window of size k by slicing the array and computing the sum each time.

• Array slicing takes O(k)
• Summing also takes O(k)
• This happens for each window → O(n) times

Overall time complexity becomes O(n × k), which causes TLE for large inputs.

This solution works logically but is inefficient due to repeated recalculation of sums.

---

Optimized Approach Using Prefix Sum

To avoid recalculating sums, I switched to using a prefix sum array. Each index in the prefix array stores the sum of elements from index 0 to i.

aux[i] = nums[0] + nums[1] + ... + nums[i]

This allows calculating the sum of any subarray in O(1) time.

---

Why Subtract aux[l-1] and Not aux[l]?

This was the most important realization and only became clear after doing a dry run on paper.

To calculate the sum of a window from index l to r:

sum = aux[r] - aux[l-1]

Reason:

• aux[r] contains sum from 0 → r
• aux[l-1] removes elements before the window

If we subtract aux[l], we incorrectly remove nums[l] itself, which belongs to the window.

---

Dry Run Example

Input:

nums = [1, 12, -5, -6, 50, 3]
k = 4

Prefix Sum:

aux = [1, 13, 8, 2, 52, 55]

Window [1 → 4] → [12, -5, -6, 50]

Correct sum:

aux[4] - aux[0] = 52 - 1 = 51

Wrong subtraction:

aux[4] - aux[1] = 52 - 13 = 39 (incorrect)

This confirmed that l-1 is mandatory.

---

Final Time Complexity

• Prefix sum creation → O(n)
• Sliding window traversal → O(n)
• Total → O(n)

This optimized solution passes all test cases efficiently.

---

Key Learning

This problem reinforced an important pattern:

Prefix sum at index i represents the sum up to i, so to start a window at l, subtract l-1.

This concept appears repeatedly in sliding window and range sum problems and is worth remembering.