Maximum Average Subarray II

This page explains Java solution to problem Maximum Average Subarray II using Binary Search algorithm.

Problem Statement

Given an array consisting of n integers, find the contiguous subarray whose length is greater than or equal to k that has the maximum average value. And you need to output the maximum average value.

Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75

Solution

If you have any suggestions in below code, please create a pull request by clicking here.

package com.vc.hard;

class MaximumAverageSubarrayIi {
    public double findMaxAverage(int[] nums, int k) {
        double lo = Integer.MAX_VALUE;
        double hi = Integer.MIN_VALUE;

        for(int i = 0; i < nums.length; i++) {
            lo = Math.min(lo, nums[i]);
            hi = Math.max(hi, nums[i]);
        }


        double avg = 0;
        while(hi - lo > 1e-5) {
            avg = lo + (hi - lo) / 2;
            if(isLargerAvgPossible(nums, k, avg)) lo = avg;
            else hi = avg;
        }
        return lo;
    }

    private boolean isLargerAvgPossible(int[] arr, int k, double avg) {
        double[] remaining = new double[arr.length];
        for(int i = 0; i < arr.length; i++) {
            remaining[i] = arr[i] - avg;
        }

        //After removing avg, check if rightSum can be > 0
        double rightSum = 0;
        double leftSum = 0;
        for(int i = 0; i < k; i++) rightSum += remaining[i];
        if(rightSum >= 0) return true;

        for(int i = k; i < arr.length; i++) {
            rightSum += remaining[i];
            leftSum += remaining[i - k];
            if(leftSum < 0) {
                rightSum -= leftSum;
                leftSum = 0;
            }
            if(rightSum >= 0) return true;
        }
        return false;
    }
}

Time Complexity

O(N log (MAX_VALUE - MIN_VALUE)) Where
N is total number of elements in an input array
MAX_VALUE is max value from input array
MIN_VALUE is min value from input array

Space Complexity

O(N) Where
N is total number of elements in an input array