Maximum Average Subarray I

easy

Last Updated - 10/09/2024

Problem Statement Solution 1: Sliding Window Approach Solution 2: Prefix Sum Approach Solution 3: Sliding Window with Manual Averaging Solution 4: Sliding Window with Two Pointers Solution 5: Sliding Window with Manual Average Calculation Solution 6: Sliding Window with Incremental Update Solution 7: Sliding Window with Sum Update More Problems Solutions

Problem Statement

You are given an array of integers, nums, with n elements, and an integer k. Your goal is to find the contiguous subarray of length k that has the highest average value. Return this maximum average, ensuring that your answer is accurate within an error margin of less than 10^-5.

Example 1

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

Output: 12.75000

Example 2

Input: nums = [5] , k = 1

Output: 5.00000

Constraints

The number of elements n in the array and the length of the subarray k satisfy: 1 ≤ k ≤ n ≤ 100,000
Each element in the array satisfies: -10,000 ≤ nums[i] ≤ 10,000
The length of the array n is equal to the length of the nums array: n = nums.length

Solution 1: Sliding Window Approach

function findMaxAverageSlidingWindow(nums, k) {
    let windowSum = 0;
    let maxAverage = -Infinity;

    for (let i = 0; i < nums.length; i++) {
        windowSum += nums[i];
        if (i >= k - 1) {
            if (i >= k) {
                windowSum -= nums[i - k];
            }
            const average = windowSum / k;
            maxAverage = Math.max(maxAverage, average);
        }
    }

    return maxAverage;
} 

const nums1 = [1,12,-5,-6,50,3];
const k1 = 4;
findMaxAverageSlidingWindow(nums1,k1);  //output: 12.75000 

const nums2 = [5];
const k2 = 1;
findMaxAverageSlidingWindow(nums2,k2);  //output: 5.00000

Solution 2: Prefix Sum Approach

function findMaxAveragePrefixSum(nums, k) {
    const prefixSum = [0];
    
    for (let i = 0; i < nums.length; i++) {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }

    let maxAverage = -Infinity;

    for (let i = k; i <= nums.length; i++) {
        const sum = prefixSum[i] - prefixSum[i - k];
        const average = sum / k;
        maxAverage = Math.max(maxAverage, average);
    }

    return maxAverage;
} 

const nums1 = [1,12,-5,-6,50,3];
const k1 = 4;
findMaxAveragePrefixSum(nums1,k1);  //output: 12.75000 

const nums2 = [5];
const k2 = 1;
findMaxAveragePrefixSum(nums2,k2);  //output: 5.00000

Solution 3: Sliding Window with Manual Averaging

function findMaxAverageSlidingWindowManual(nums, k) {
    let currArr = nums.slice(0, k);
    let currAvg = currArr.reduce((sum, num) => sum + num, 0) / k;
    let maxAvg = currAvg;

    for (let i = 1; i <= nums.length - k; i++) {
        currAvg -= nums[i - 1] / k;
        currArr = nums.slice(i, i + k);
        currAvg += currArr[currArr.length - 1] / k;
        maxAvg = Math.max(maxAvg, currAvg);
    }

    return maxAvg;
} 

const nums1 = [1,12,-5,-6,50,3];
const k1 = 4;
findMaxAverageSlidingWindowManual(nums1,k1);  //output: 12.75000 

const nums2 = [5];
const k2 = 1;
findMaxAverageSlidingWindowManual(nums2,k2);  //output: 5.00000

Solution 4: Sliding Window with Two Pointers

function findMaxAverageSlidingWindowTwoPointers(nums, k) {
    let maxAverage = -Infinity;
    let sum = 0;
    let left = 0;
    
    for (let right = 0; right < nums.length; right++) {
        sum += nums[right];
        
        if (right - left + 1 === k) {
            let average = sum / k;
            maxAverage = Math.max(maxAverage, average);
            sum -= nums[left];
            left++;
        }
    }
    
    return maxAverage;
} 

const nums1 = [1,12,-5,-6,50,3];
const k1 = 4;
findMaxAverageSlidingWindowTwoPointers(nums1,k1);  //output: 12.75000 

const nums2 = [5];
const k2 = 1;
findMaxAverageSlidingWindowTwoPointers(nums2,k2);  //output: 5.00000

Solution 5: Sliding Window with Manual Average Calculation

function findMaxAverageSlidingWindowManualAvg(nums, k) {
    let right = 0;
    let left = 0;
    const length = nums.length;
    let maxAvg = 0.0;
    let windowAvg = 0.0;

    // Initialize the window
    while (right < k) {
        windowAvg += nums[right] / k;
        right++;
    }
    maxAvg = windowAvg;

    // Slide the window
    while (right < length) {
        windowAvg = windowAvg - nums[left] / k + nums[right] / k;
        left++;
        if (windowAvg > maxAvg) {
            maxAvg = windowAvg;
        }
        right++;
    }

    return maxAvg;
} 

const nums1 = [1,12,-5,-6,50,3];
const k1 = 4;
findMaxAverageSlidingWindowManualAvg(nums1,k1);  //output: 12.75000 

const nums2 = [5];
const k2 = 1;
findMaxAverageSlidingWindowManualAvg(nums2,k2);  //output: 5.00000

Solution 6: Sliding Window with Incremental Update

function findMaxAverageSlidingWindowIncremental(nums, k) {
    let maxAvg = nums.slice(0, k).reduce((sum, num) => sum + num, 0) / k;
    let currAvg = maxAvg;

    for (let i = k; i < nums.length; i++) {
        currAvg = currAvg + (nums[i] - nums[i - k]) / k;
        maxAvg = Math.max(maxAvg, currAvg);
    }

    return parseFloat(maxAvg.toFixed(5));
} 

const nums1 = [1,12,-5,-6,50,3];
const k1 = 4;
findMaxAverageSlidingWindowIncremental(nums1,k1);  //output: 12.75000 

const nums2 = [5];
const k2 = 1;
findMaxAverageSlidingWindowIncremental(nums2,k2);  //output: 5.00000

Solution 7: Sliding Window with Sum Update

function findMaxAverageSlidingWindowSumUpdate(nums, k) {
    let curSum = nums.slice(0, k).reduce((sum, num) => sum + num, 0);
    let maxSum = curSum;

    for (let i = k; i < nums.length; i++) {
        curSum += nums[i] - nums[i - k];
        if (curSum > maxSum) {
            maxSum = curSum;
        }
    }

    return maxSum / k;
} 

const nums1 = [1,12,-5,-6,50,3];
const k1 = 4;
findMaxAverageSlidingWindowSumUpdate(nums1,k1);  //output: 12.75000 

const nums2 = [5];
const k2 = 1;
findMaxAverageSlidingWindowSumUpdate(nums2,k2);  //output: 5.00000