Problem

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

Find a contiguous subarray whose length is greater than or 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
4
5
6
7

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: - When the length is 4, averages are [0.5, 12.75, 10.5] and the maximum average is 12.75
- When the length is 5, averages are [10.4, 10.8] and the maximum average is 10.8
- When the length is 6, averages are [9.16667] and the maximum average is 9.16667
The maximum average is when we choose a subarray of length 4 (i.e., the sub array [12, -5, -6, 50]) which has the max average 12.75, so we return 12.75
Note that we do not consider the subarrays of length < 4.

Example 2:

1
2

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

Constraints:

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

Solution

Method 1 – Binary Search + Prefix Sum

Intuition

To find the maximum average subarray of length at least k, we can use binary search on the answer. For a candidate average, we check if there exists a subarray of length at least k whose average is at least that value. This can be checked using prefix sums and maintaining the minimum prefix sum for the window.

Approach

  1. Set left and right bounds for binary search as the min and max of nums.
  2. While right - left > 1e-5:
    • Set mid = (left + right) / 2.
    • Check if there exists a subarray of length at least k with average >= mid:
      • Subtract mid from each element and compute prefix sums.
      • For each i >= k, check if prefix[i] - min(prefix[0..i-k]) >= 0.
    • If possible, set left = mid; else, set right = mid.
  3. Return left as the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double l = *min_element(nums.begin(), nums.end()), r = *max_element(nums.begin(), nums.end());
        while (r - l > 1e-5) {
            double m = (l + r) / 2;
            vector<double> s(nums.size()+1);
            for (int i = 0; i < nums.size(); ++i) s[i+1] = s[i] + nums[i] - m;
            double min_pre = 0, ok = 0;
            for (int i = k; i <= nums.size(); ++i) {
                if (s[i] - min_pre >= 0) ok = 1;
                min_pre = min(min_pre, s[i-k+1]);
            }
            if (ok) l = m; else r = m;
        }
        return l;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func findMaxAverage(nums []int, k int) float64 {
    l, r := float64(nums[0]), float64(nums[0])
    for _, x := range nums {
        if float64(x) < l { l = float64(x) }
        if float64(x) > r { r = float64(x) }
    }
    for r-l > 1e-5 {
        m := (l + r) / 2
        s := make([]float64, len(nums)+1)
        for i := 0; i < len(nums); i++ {
            s[i+1] = s[i] + float64(nums[i]) - m
        }
        minPre, ok := 0.0, false
        for i := k; i <= len(nums); i++ {
            if s[i]-minPre >= 0 {
                ok = true
            }
            if s[i-k+1] < minPre {
                minPre = s[i-k+1]
            }
        }
        if ok {
            l = m
        } else {
            r = m
        }
    }
    return l
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double l = Arrays.stream(nums).min().getAsInt(), r = Arrays.stream(nums).max().getAsInt();
        while (r - l > 1e-5) {
            double m = (l + r) / 2;
            double[] s = new double[nums.length+1];
            for (int i = 0; i < nums.length; ++i) s[i+1] = s[i] + nums[i] - m;
            double minPre = 0;
            boolean ok = false;
            for (int i = k; i <= nums.length; ++i) {
                if (s[i] - minPre >= 0) ok = true;
                minPre = Math.min(minPre, s[i-k+1]);
            }
            if (ok) l = m; else r = m;
        }
        return l;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun findMaxAverage(nums: IntArray, k: Int): Double {
        var l = nums.minOrNull()!!.toDouble()
        var r = nums.maxOrNull()!!.toDouble()
        while (r - l > 1e-5) {
            val m = (l + r) / 2
            val s = DoubleArray(nums.size+1)
            for (i in nums.indices) s[i+1] = s[i] + nums[i] - m
            var minPre = 0.0
            var ok = false
            for (i in k..nums.size) {
                if (s[i] - minPre >= 0) ok = true
                minPre = minOf(minPre, s[i-k+1])
            }
            if (ok) l = m else r = m
        }
        return l
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def findMaxAverage(self, nums: list[int], k: int) -> float:
        l, r = min(nums), max(nums)
        while r - l > 1e-5:
            m = (l + r) / 2
            s = [0]
            for x in nums:
                s.append(s[-1] + x - m)
            min_pre = 0
            ok = False
            for i in range(k, len(nums)+1):
                if s[i] - min_pre >= 0:
                    ok = True
                min_pre = min(min_pre, s[i-k+1])
            if ok:
                l = m
            else:
                r = m
        return l
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

impl Solution {
    pub fn find_max_average(nums: Vec<i32>, k: i32) -> f64 {
        let (mut l, mut r) = (*nums.iter().min().unwrap() as f64, *nums.iter().max().unwrap() as f64);
        while r - l > 1e-5 {
            let m = (l + r) / 2.0;
            let mut s = vec![0.0; nums.len()+1];
            for i in 0..nums.len() {
                s[i+1] = s[i] + nums[i] as f64 - m;
            }
            let mut min_pre = 0.0;
            let mut ok = false;
            for i in k as usize..=nums.len() {
                if s[i] - min_pre >= 0.0 {
                    ok = true;
                }
                min_pre = min_pre.min(s[i-k as usize+1]);
            }
            if ok {
                l = m;
            } else {
                r = m;
            }
        }
        l
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    findMaxAverage(nums: number[], k: number): number {
        let l = Math.min(...nums), r = Math.max(...nums);
        while (r - l > 1e-5) {
            const m = (l + r) / 2;
            const s = [0];
            for (const x of nums) s.push(s[s.length-1] + x - m);
            let minPre = 0, ok = false;
            for (let i = k; i <= nums.length; ++i) {
                if (s[i] - minPre >= 0) ok = true;
                minPre = Math.min(minPre, s[i-k+1]);
            }
            if (ok) l = m; else r = m;
        }
        return l;
    }
}

Complexity

  • ⏰ Time complexity: O(n log W), where W is the range of values in nums, due to binary search and prefix sum check.
  • 🧺 Space complexity: O(n), for the prefix sum array.