Maximum Average Subarray I

LeetCode 643 | Difficulty: Easy

Easy

Problem Description

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10^-5 will be accepted.

Example 1:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (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 <= 10^5`

- `-10^4 <= nums[i] <= 10^4`

Topics: Array, Sliding Window

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

---

Solutions

Solution 1: C# (Best: 304 ms)

Metric	Value
Runtime	304 ms
Memory	45.4 MB
Date	2021-12-02

Solution

public class Solution {
    public double FindMaxAverage(int[] nums, int k) {
       int n = nums.Length;
    double sum = 0;
    double max = double.MinValue;
    int left = 0;
    for (int i = 0; i < n; i++)
    {
        sum += nums[i];
        if(i>=k-1)
        {
            max = Math.Max(sum, max);
            sum -= nums[left++];            
        }
    }

    return max/k;
        
    }
}

---

Complexity Analysis

Approach	Time	Space
Sliding Window	$O(n)$	$O(k)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.