Maximum Average Subarray I
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.
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 <= 105
- -104 <= nums[i] <= 104
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The basic idea behind the brute force approach is to calculate the sum of every possible subarray of length k and then find the one with the maximum sum. This approach involves iterating over all the subarrays of length k, which can be computationally expensive for larger arrays.
Code:
- Time Complexity: O(n * k), where
nis the length ofnums. We calculate the sum for each possible subarray starting from each index. - Space Complexity: O(1), only a fixed amount of extra space is used.
2. Sliding Window
Intuition:
The sliding window approach optimizes the calculation of the subarray sum by re-using the sum of the previous subarray. Rather than recalculating the sum from scratch for each subarray, we adjust the sum by subtracting the element that slides out of the window and adding the new element that comes into the window.
Code:
- Time Complexity: O(n), where
nis the length ofnums. We traverse the array once. - Space Complexity: O(1), as we are using a constant amount of extra space.