Maximum Average Subarray II

hard binary search sliding window

Problem

Find the maximum possible average over any contiguous subarray of length at least k.

Inputnums=[1,12,-5,-6,50,3] k=4

Output12.75

Window [50,12,-5,-6] gives avg 12.75 (length 4).

input

def find_max_average(nums, k):
    def can(x):
        pre = mn = 0; s = 0
        for i, v in enumerate(nums):
            s += v - x
            if i >= k - 1:
                if s - mn >= 0: return True
                pre += nums[i - k + 1] - x; mn = min(mn, pre)
        return False
    lo, hi = min(nums), max(nums)
    while hi - lo > 1e-5:
        m = (lo + hi) / 2
        if can(m): lo = m
        else: hi = m
    return lo

function findMaxAverage(nums, k) {
  const can = x => {
    let pre = 0, mn = 0, s = 0;
    for (let i = 0; i < nums.length; i++) {
      s += nums[i] - x;
      if (i >= k - 1) {
        if (s - mn >= 0) return true;
        pre += nums[i - k + 1] - x; mn = Math.min(mn, pre);
      }
    }
    return false;
  };
  let lo = Math.min(...nums), hi = Math.max(...nums);
  while (hi - lo > 1e-5) { const m = (lo + hi) / 2; if (can(m)) lo = m; else hi = m; }
  return lo;
}

double findMaxAverage(int[] nums, int k) {
    double lo = Arrays.stream(nums).min().getAsInt(), hi = Arrays.stream(nums).max().getAsInt();
    while (hi - lo > 1e-5) {
        double m = (lo + hi) / 2;
        if (can(nums, k, m)) lo = m; else hi = m;
    }
    return lo;
}
boolean can(int[] nums, int k, double x) {
    double pre = 0, mn = 0, s = 0;
    for (int i = 0; i < nums.length; i++) {
        s += nums[i] - x;
        if (i >= k - 1) {
            if (s - mn >= 0) return true;
            pre += nums[i - k + 1] - x; mn = Math.min(mn, pre);
        }
    }
    return false;
}

bool can(vector& nums, int k, double x) {
    double pre = 0, mn = 0, s = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        s += nums[i] - x;
        if (i >= k - 1) {
            if (s - mn >= 0) return true;
            pre += nums[i - k + 1] - x; mn = min(mn, pre);
        }
    }
    return false;
}
double findMaxAverage(vector& nums, int k) {
    double lo = *min_element(nums.begin(), nums.end()), hi = *max_element(nums.begin(), nums.end());
    while (hi - lo > 1e-5) { double m = (lo + hi) / 2; if (can(nums, k, m)) lo = m; else hi = m; }
    return lo;
}

Explanation

We do not search the subarrays directly. Instead we binary-search the answer average x and ask a yes/no question: is there a subarray of length at least k whose average is at least x?

The clever trick is to subtract x from every element. Now "average ≥ x" becomes "sum of the shifted values ≥ 0". So can(x) just needs to find a window of length ≥ k with a non-negative shifted sum.

Using a running prefix sum s, the sum of a window ending at i is s - (prefix before the window). To maximize it, we track the minimum earlier prefix mn (only prefixes that leave at least k elements). If s - mn >= 0 at any point, a valid window exists and we return true.

If can(x) is true, that average is reachable so we push lo up; otherwise we pull hi down. We stop once hi - lo is below a tiny epsilon like 1e-5, giving the answer to enough precision.

Example: nums=[1,12,-5,-6,50,3], k=4. The window [50,12,-5,-6] averages 12.75, and the search converges right on 12.75.

Time: O(n log((hi−lo)/eps)) Space: O(1)