Maximum average subarray ii

Array Binary Search Prefix Sum

37.7% acceptance

Mar 31, 2026

639

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.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn find_max_average(nums: Vec<i32>, k: i32) -> f64 {
    let n = nums.len();
    let k = k as usize;
    let mut lo = *nums.iter().min().unwrap() as f64;
    let mut hi = *nums.iter().max().unwrap() as f64;
    while hi - lo > 1e-6 {
      let mid = (lo + hi) / 2.0;
      // Check if there exists a subarray of length >= k with average >= mid
      let mut sum = 0.0;
      for i in 0..k {
        sum += nums[i] as f64 - mid;
      }
      if sum >= 0.0 {
        lo = mid;
        continue;
      }
      let mut prev_sum: f64 = 0.0;
      let mut min_prev: f64 = 0.0;
      let mut found = false;
      for i in k..n {
        sum += nums[i] as f64 - mid;
        prev_sum += nums[i - k] as f64 - mid;
        min_prev = min_prev.min(prev_sum);
        if sum - min_prev >= 0.0 {
          found = true;
          break;
        }
      }
      if found {
        lo = mid;
      } else {
        hi = mid;
      }
    }
    lo
  }
}