643. Maximum Average Subarray I
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 42.0%
Problem Breakdown
The problem asks us to find the contiguous subarray of length k within an array of integers that has the maximum average value. The output should be the maximum average value itself.
Inputs:
- An array of integers
numswith lengthn. - An integer
krepresenting the length of the subarray.
Outputs:
- A floating-point number representing the maximum average value of any contiguous subarray of length
k.
Implicit Constraints or Tricky Edge Cases:
- The array can contain negative numbers.
- The array can have duplicate values.
- The edge case where
n = k(the entire array is the subarray). - The edge case where all elements are negative.
Intuition
A brute-force approach would involve calculating the average of every possible contiguous subarray of length k and keeping track of the maximum. This approach would have a time complexity of O(n*k), which is inefficient for large arrays (up to 30,000 elements).
The key insight is to use a sliding window technique. By maintaining a running sum of the current window of size k, we can efficiently calculate the average in constant time as we slide the window across the array. This reduces the time complexity to O(n), making it much more efficient.
Approach
-
Initialize Variables:
- Calculate the sum of the first
kelements to initialize the running sum. - Set this initial sum as the maximum sum found so far.
- Calculate the sum of the first
-
Sliding Window Technique:
- Slide the window one element at a time from the start of the array to the end.
- For each new position, update the running sum by subtracting the element that is sliding out of the window and adding the new element that is sliding into the window.
- Update the maximum sum if the current running sum is greater than the previously recorded maximum sum.
-
Calculate Maximum Average:
- Once all possible windows have been considered, calculate the maximum average by dividing the maximum sum by
k.
- Once all possible windows have been considered, calculate the maximum average by dividing the maximum sum by
Complexity Analysis
- Time Complexity: O(n) because we only pass through the array once.
- Space Complexity: O(1) because we are using a constant amount of extra space.
Solution
def findMaxAverage(nums, k):
# Calculate the sum of the first window of size k
max_sum = current_sum = sum(nums[:k])
# Slide the window across the array
for i in range(k, len(nums)):
# Update the running sum by subtracting the element that is sliding out
# and adding the new element that is sliding into the window
current_sum += nums[i] - nums[i - k]
# Update max_sum if the current_sum is greater
max_sum = max(max_sum, current_sum)
# Return the maximum average
return max_sum / k
# Example usage:
nums = [1, 12, -5, -6, 50, 3]
k = 4
print(findMaxAverage(nums, k)) # Output: 12.75
Edge Cases Handled
- Single Element Array (
n = k): The initial sum will be the maximum sum since there’s only one possible subarray. - All Negative Numbers: The algorithm correctly identifies the maximum average among negative numbers.
- Array with Duplicates: The sliding window approach naturally handles duplicates without any special logic.