Problem Statement

Given an array of integers and an integer k, find a contiguous subarray of length k that has the highest average value, and return this maximum average value.

Examples

Example 1

• Input: nums = [1, 2, 3, 4, 5, 6], k = 2
• Expected Output: 5.5
• Justification: The subarray [5, 6] has the highest average (5 + 6) / 2 = 5.5.

Example 2

• Input: nums = [0, 1, 1, 3, -1, 10, -2], k = 3
• Expected Output: 4.0
• Justification: The subarray [3, -1, 10] has the highest average (3 + (-1) + 10) / 3 = 4.0.

Example 3

• Input: nums = [-5, -2, 0, 3, 9, -1, 2], k = 4
• Expected Output: 3.25
• Justification: The subarray [3, 9, -1, 2] has the highest average (3 + 9 + (-1) + 2) / 4 = 3.25.

Constraints:

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

Solution

To solve this problem, we need to find a subarray of length ( k ) with the highest average. We can use a sliding window approach to efficiently calculate the sum of subarrays. By maintaining a window of size ( k ) and sliding it across the array, we can update the sum by subtracting the element that goes out of the window and adding the new element that enters the window. This approach ensures that we only need to pass through the array once, making it efficient in terms of time complexity.

The sliding window method is effective because it reduces the need for nested loops, which would result in higher time complexity. Instead, by adjusting the window's sum dynamically as it slides, we achieve the desired result in linear time. This makes our approach both time-efficient and easy to implement.

Step-by-Step Algorithm

• Initialize the sum of the first ( k ) elements and store it in a variable, say currentSum.
• Initialize a variable maxSum with the value of currentSum.
• Iterate through the array starting from the ( k )-th element to the end:
  • For each element, update currentSum by adding the current element and subtracting the element that is ( k ) positions behind.
  • Update maxSum if currentSum is greater than maxSum.
• Return the maximum average by dividing maxSum by ( k ).

Algorithm Walkthrough

Step-by-Step Algorithm Walkthrough

Let's consider the example input nums = [-5, -2, 0, 3, 9, -1, 2], k = 4.

1. Initialization:

   • Input array: [-5, -2, 0, 3, 9, -1, 2]
   • Subarray length (k): 4
   • Calculate the initial sum of the first k elements: sum([-5, -2, 0, 3]) = -5 + (-2) + 0 + 3 = -4
   • Set maxSum to this initial sum: maxSum = -4
   • Initialize currentSum to maxSum: currentSum = -4

2. Sliding Window:

   • Start sliding the window from the k-th element (index 4) to the end of the array.

   • First Slide (i = 4):

     • Add the next element nums[4] = 9 and remove the first element of the previous window nums[0] = -5:
       • currentSum = currentSum + nums[4] - nums[0] = -4 + 9 - (-5) = 10
     • Update maxSum if currentSum is greater:
       • maxSum = max(maxSum, currentSum) = max(-4, 10) = 10

   • Second Slide (i = 5):

     • Add the next element nums[5] = -1 and remove the first element of the previous window nums[1] = -2:
       • currentSum = currentSum + nums[5] - nums[1] = 10 + (-1) - (-2) = 11
     • Update maxSum if currentSum is greater:
       • maxSum = max(maxSum, currentSum) = max(10, 11) = 11

   • Third Slide (i = 6):

     • Add the next element nums[6] = 2 and remove the first element of the previous window nums[2] = 0:
       • currentSum = currentSum + nums[6] - nums[2] = 11 + 2 - 0 = 13
     • Update maxSum if currentSum is greater:
       • maxSum = max(maxSum, currentSum) = max(11, 13) = 13

3. Calculate the Maximum Average:

   • The final maximum sum of any subarray of length k is maxSum = 13.
   • The maximum average is maxSum / k = 13 / 4 = 3.25.

Complexity Analysis

• Time Complexity: The algorithm iterates through the array once, making it O(n), where n is the number of elements in the array. This is efficient because it only requires a single pass to compute the sum of the subarrays.

• Space Complexity: The space complexity is O(1) because we are using a fixed amount of extra space regardless of the input size.