643. Maximum Average Subarray I

Jump to Solution: Python Java C++ JavaScript C#

Problem Description

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

Find a contiguous subarray whose length is 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:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Example 2:

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

Constraints:

n == nums.length
1 ≤ k ≤ n ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴

Python Solution

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        # Initialize the sum of first k elements
        curr_sum = sum(nums[:k])
        max_sum = curr_sum
        
        # Slide the window and keep track of maximum sum
        for i in range(k, len(nums)):
            curr_sum = curr_sum + nums[i] - nums[i - k]
            max_sum = max(max_sum, curr_sum)
        
        # Return the maximum average
        return max_sum / k

Alternative Solution (Using Prefix Sum):

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        # Calculate prefix sums
        prefix_sum = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            prefix_sum[i + 1] = prefix_sum[i] + nums[i]
        
        # Find maximum sum of k consecutive elements
        max_sum = float('-inf')
        for i in range(k, len(prefix_sum)):
            curr_sum = prefix_sum[i] - prefix_sum[i - k]
            max_sum = max(max_sum, curr_sum)
        
        return max_sum / k

Implementation Notes:

First solution uses sliding window technique with O(n) time and O(1) space
Second solution uses prefix sum with O(n) time and O(n) space
Both solutions handle edge cases where k equals array length

Java Solution

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        // Initialize sum of first k elements
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        
        int maxSum = sum;
        
        // Slide window and track maximum sum
        for (int i = k; i < nums.length; i++) {
            sum = sum + nums[i] - nums[i - k];
            maxSum = Math.max(maxSum, sum);
        }
        
        return (double) maxSum / k;
    }
}

C++ Solution

class Solution {
public:
    double findMaxAverage(vector& nums, int k) {
        // Initialize sum of first k elements
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        
        int maxSum = sum;
        
        // Slide window and track maximum sum
        for (int i = k; i < nums.size(); i++) {
            sum = sum + nums[i] - nums[i - k];
            maxSum = max(maxSum, sum);
        }
        
        return static_cast(maxSum) / k;
    }
};

JavaScript Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findMaxAverage = function(nums, k) {
    // Initialize sum of first k elements
    let sum = 0;
    for (let i = 0; i < k; i++) {
        sum += nums[i];
    }
    
    let maxSum = sum;
    
    // Slide window and track maximum sum
    for (let i = k; i < nums.length; i++) {
        sum = sum + nums[i] - nums[i - k];
        maxSum = Math.max(maxSum, sum);
    }
    
    return maxSum / k;
};

C# Solution

public class Solution {
    public double FindMaxAverage(int[] nums, int k) {
        // Initialize sum of first k elements
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        
        int maxSum = sum;
        
        // Slide window and track maximum sum
        for (int i = k; i < nums.Length; i++) {
            sum = sum + nums[i] - nums[i - k];
            maxSum = Math.Max(maxSum, sum);
        }
        
        return (double)maxSum / k;
    }
}

Alternative Solution (Using LINQ):

public class Solution {
    public double FindMaxAverage(int[] nums, int k) {
        return Enumerable.Range(0, nums.Length - k + 1)
            .Select(i => nums.Skip(i).Take(k).Average())
            .Max();
    }
}

Implementation Notes:

First solution uses sliding window technique for optimal performance
Second solution uses LINQ for cleaner but less efficient implementation
Both solutions handle floating-point arithmetic correctly