Problem

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.

Examples

Example 1

1
2
3

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

1
2

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

Constraints

  • n == nums.length
  • 1 <= k <= n <= 10^5
  • -10^4 <= nums[i] <= 10^4

Solution

Method 1 – Sliding Window

Intuition

To find the maximum average of a subarray of length k, we can use a sliding window of size k and keep track of the sum as we move the window. This allows us to efficiently compute the sum for each window in O(1) time after the first window.

Approach

  1. Compute the sum of the first k elements.
  2. Slide the window from left to right:
    • Subtract the element leaving the window and add the new element entering the window.
    • Track the maximum sum seen so far.
  3. Return the maximum sum divided by k as the maximum average.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int n = nums.size();
        double sum = 0, ans = -1e9;
        for (int i = 0; i < k; ++i) sum += nums[i];
        ans = sum;
        for (int i = k; i < n; ++i) {
            sum += nums[i] - nums[i-k];
            ans = max(ans, sum);
        }
        return ans / k;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func findMaxAverage(nums []int, k int) float64 {
    n := len(nums)
    sum := 0
    for i := 0; i < k; i++ {
        sum += nums[i]
    }
    ans := sum
    for i := k; i < n; i++ {
        sum += nums[i] - nums[i-k]
        if sum > ans {
            ans = sum
        }
    }
    return float64(ans) / float64(k)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        double sum = 0, ans = -1e9;
        for (int i = 0; i < k; ++i) sum += nums[i];
        ans = sum;
        for (int i = k; i < n; ++i) {
            sum += nums[i] - nums[i-k];
            ans = Math.max(ans, sum);
        }
        return ans / k;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun findMaxAverage(nums: IntArray, k: Int): Double {
        val n = nums.size
        var sum = 0.0
        for (i in 0 until k) sum += nums[i]
        var ans = sum
        for (i in k until n) {
            sum += nums[i] - nums[i-k]
            ans = maxOf(ans, sum)
        }
        return ans / k
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def findMaxAverage(self, nums: list[int], k: int) -> float:
        n = len(nums)
        s = sum(nums[:k])
        ans = s
        for i in range(k, n):
            s += nums[i] - nums[i-k]
            ans = max(ans, s)
        return ans / k
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn find_max_average(nums: Vec<i32>, k: i32) -> f64 {
        let n = nums.len();
        let mut sum: i32 = nums[..k as usize].iter().sum();
        let mut ans = sum;
        for i in k as usize..n {
            sum += nums[i] - nums[i-k as usize];
            ans = ans.max(sum);
        }
        ans as f64 / k as f64
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    findMaxAverage(nums: number[], k: number): number {
        let sum = 0;
        for (let i = 0; i < k; ++i) sum += nums[i];
        let ans = sum;
        for (let i = k; i < nums.length; ++i) {
            sum += nums[i] - nums[i-k];
            ans = Math.max(ans, sum);
        }
        return ans / k;
    }
}

Complexity

  • ⏰ Time complexity: O(n), since we process each element once.
  • 🧺 Space complexity: O(1), only a constant number of variables are used.