Skip to main content

Maximum Average Subarray I

— Prerna Sharma

Maximum Average Subarray I

Maximum Average Subarray I – LeetCode #643 | DSA for Beginners

Brute force nested loops → Sliding Window. Learn why we slide instead of re-sum.

Easy Sliding Window Array

Problem Statement

Given

An integer array nums of n elements and an integer k. Find a contiguous subarray whose length equals k that has the maximum average value. Return that average.

Examples

Example 1
Input: nums = [1, 12, -5, -6, 50, 3], k = 4
Output: 12.75000
Explanation: Max average = (12 − 5 − 6 + 50) / 4 = 51 / 4 = 12.75

Example 2
Input: nums = [5], k = 1
Output: 5.00000

Constraints: n == nums.length  •  1 ≤ k ≤ n ≤ 105  •  −104 ≤ nums[i] ≤ 104
Answers within 10−5 of the true answer are accepted.

What Are We Looking For? 🧠

We want the window of k consecutive numbers that has the highest average. Average = sum / k. Since k is fixed, maximising the average is the same as maximising the sum. So the problem reduces to: find the contiguous subarray of length exactly k with the biggest sum.

nums = [1, 12, −5, −6, 50, 3]  |  k = 4  —  all possible windows:

1
0
12
1
−5
2
−6
3
50
4
3
5

▶ Window 1 (idx 0–3): 1+12−5−6 = 2  →  avg = 0.5

1
0
12
1
−5
2
−6
3
50
4
3
5

▶ Window 2 (idx 1–4): 12−5−6+50 = 51  →  avg = 12.75 ✅ BEST

1
0
12
1
−5
2
−6
3
50
4
3
5

▶ Window 3 (idx 2–5): −5−6+50+3 = 42  →  avg = 10.5

Approaches at a Glance

🐌 Brute Force (Nested Loops)

Outer loop picks each window start. Inner loop sums the k elements. Check all windows.

Time: O(n × k) Space: O(1)

⚡ Sliding Window (Optimal)

Reuse the previous window sum. Subtract one element, add one element. One pass only.

Time: O(n) Space: O(1)

Approach 1 — Brute Force (Nested Loops)

The straightforward idea: for every valid starting index i (from 0 to n−k), sum the next k elements (indices i to i+k−1), compute the average, and track the maximum.

  • Initialise maxAvg to the average of the very first window (so negative numbers don’t break the comparison).
  • Outer loop: i from 0 to n−k inclusive — each position is a window start.
  • Inner loop: j from i to i+k−1 — sum the window’s k elements.
  • Compute average = windowSum / k. Update maxAvg if this is bigger.
  • Return maxAvg after all windows are checked.


  
  
🔍 Dry Run — Brute Force

  
Input: nums = [1, 12, −5, −6, 50, 3], k = 4

  
n = 6, so outer loop runs i = 0, 1, 2  (i ≤ n−k = 2)


  

    
      
i (start)j rangeElements summedwindowSumavgmaxAvg

    
    
      

        00 → 31, 12, −5, −6
        20.5
        0.5 (init)
      

      

        11 → 412, −5, −6, 50
        51
        12.75
        12.75 ↑
      

      

        22 → 5−5, −6, 50, 3
        4210.5
        12.75 (no change)
      

    
  


  

    Result: maxAvg = 12.75 ✅

    Problem: For each of the 3 windows, we re-summed all 4 elements from scratch. That’s 3 × 4 = 12 operations for this tiny input. With n=100,000 and k=50,000 this becomes 50,000 × 50,001 ≈ 2.5 billion operations. Way too slow!
  


  

    ⚠️ The Redundancy: When we slide from window [1, 12, −5, −6] to [12, −5, −6, 50], we re-added 12, −5, and −6 even though they were already in the previous sum. We’re doing unnecessary repeated work. This is exactly what Sliding Window eliminates.
  


  
  
Approach 2 — Sliding Window (Optimal) ⚡


  
The Key Intuition

  
Look at what changes between two consecutive windows of size k:


  

    

      

        
1

        
leaves

        
OUT

      

      
12
stays

      
−5
stays

      
−6
stays

      

        
50

        
enters

        
IN

      

    

    

      New sum = Old sum − nums[windowStart] + nums[windowEnd]
    

    

      = 2 − 1 + 50 = 51  —  no inner loop needed!
    

  


  
How the Algorithm Works

  
    
    
  • Expand windowEnd one step at a time, adding nums[windowEnd] to windowSum.
    • 
    
  • When the window size reaches exactly k (windowEnd − windowStart + 1 == k):
    • 
    
  • Update maxSum if windowSum is bigger.
    • 
    
  • Shrink the window from the left: subtract nums[windowStart] from windowSum, then advance windowStart++.
    • 
    
  • After the loop, return maxSum / k.
    • 
  


  

    💡 Why track maxSum instead of maxAvg?

    All windows are the same length k. Bigger sum → bigger average. We divide by k only once at the end, avoiding floating-point operations inside the loop.
  


  
  
🔍 Dry Run — Sliding Window

  
Input: nums = [1, 12, −5, −6, 50, 3], k = 4

  
Initial state: windowStart = 0, windowSum = 0, maxSum = 0


  

    

      windowEnd = 0
      Window size = 1, not yet k=4
    

    

      
1
0 ↑E

      
12
1

      
−5
2

      
−6
3

      
50
4

      
3
5

    

    
windowSum += nums[0] = 1  •  windowSum = 1  •  size = 1 < 4, skip

  


  

    

      windowEnd = 1
      Window size = 2, not yet k=4
    

    

      
1
0 ↑S

      
12
1 ↑E

      
−5
2

      
−6
3

      
50
4

      
3
5

    

    
windowSum += nums[1] = 12  •  windowSum = 13  •  size = 2 < 4, skip

  


  

    

      windowEnd = 2
      Window size = 3, not yet k=4
    

    

      
1
0 ↑S

      
12
1

      
−5
2 ↑E

      
−6
3

      
50
4

      
3
5

    

    
windowSum += nums[2] = −5  •  windowSum = 8  •  size = 3 < 4, skip

  


  

    

      windowEnd = 3 — FIRST FULL WINDOW 🎯
    

    

      
1
0 ↑S

      
12
1

      
−5
2

      
−6
3 ↑E

      
50
4

      
3
5

    

    
windowSum += −6  •  windowSum = 2  •  size = 4 == k  ✅
maxSum = max(0, 2) = 2
windowSum −= nums[0]=1 → windowSum = 1  •  windowStart → 1

  


  

    

      windowEnd = 4 — NEW BEST ⬆
    

    

      
1
0 (out)

      
12
1 ↑S

      
−5
2

      
−6
3

      
50
4 ↑E

      
3
5

    

    
windowSum += 50  •  windowSum = 51  •  size = 4 == k  ✅
maxSum = max(2, 51) = 51 ↑ NEW BEST!
windowSum −= nums[1]=12 → windowSum = 39  •  windowStart → 2

  


  

    

      windowEnd = 5 — LAST WINDOW
    

    

      
1
0

      
12
1 (out)

      
−5
2 ↑S

      
−6
3

      
50
4

      
3
5 ↑E

    

    
windowSum += 3  •  windowSum = 42  •  size = 4 == k  ✅
maxSum = max(51, 42) = 51 (no change)
windowSum −= nums[2]=−5 → windowSum = 47  •  windowStart → 3 (loop ends)

  


  

    🎯 Result: maxSum = 51  →  return 51 / 4 = 12.75 ✅

    Efficiency: 6 iterations total (n=6). No inner loop. Every element touched exactly once.
  


  
  
Time & Space Complexity

  

    
ApproachTimeSpaceNote

    
      

        Brute Force (Nested Loops)
        O(n × k)
        O(1)
        Re-sums k elements for every window start
      

      

        Sliding Window
        O(n)
        O(1)
        Single pass; each element added and removed once
      

    
  


  

    Key Insight: The sliding window trades the inner loop for two O(1) operations — one addition (element entering) and one subtraction (element leaving). The sum is maintained, not recomputed. This is the defining trick of the fixed-size sliding window pattern.
  


  
  
Code — All Approaches × All Languages


  
  

    

      Approach 1
      🐌 Brute Force — Nested Loops
      
        O(n × k)
        O(1) space
      
    

    

      
      
      
      
    

    

    

    

    

  


  
  

    

      Approach 2
      ⚡ Sliding Window — Fixed Size (Optimal)
      
        O(n)
        O(1) space
      
    

    

      💡 Track windowStart and windowEnd. When window hits size k: update maxSum, subtract the left element, advance start.

      Return maxSum / k once — not inside the loop.
    

    

      
      
      
      
    

    

    

    

    

  


  

  

    🎯 Interview Tip: Whenever you see “contiguous subarray of fixed length k” + “maximum / minimum / average”, reach for a fixed-size sliding window. The pattern is always the same: expand right, check size, update answer, shrink left. Master this and 3Sum, Max Consecutive Ones III, and Longest Subarray with Limit all become straightforward variations.