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.length1 <= k <= n <= 105-104 <= nums[i] <= 104The sliding window technique allows us to keep track of the sum of a subarray of fixed length k by adding one new element and removing the first element of the previous window, thus achieving O(n) time complexity.
The C code initializes a sum of the first k elements and iterates over the elements from k to the end of the array. It updates the sum to add the current element and subtract the element that is sliding out of the window, then updates maxSum if the new sum is greater. Finally, it returns the maximum average.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
The brute force approach involves checking every possible subarray of length k and calculating its average, then keeping track of the maximum average found. However, this approach is not efficient for large inputs.
The C solution calculates the sum and average of every subarray of length k, updating the maximum average found. This implementation is simple but inefficient for large arrays due to its O(n*k) complexity.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n*k)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Using Sliding Window Technique | Time Complexity: O(n) |
| Brute Force Approach | Time Complexity: O(n*k) |
Maximum Subarray - Amazon Coding Interview Question - Leetcode 53 - Python • NeetCode • 605,117 views views
Watch 9 more video solutions →Practice Maximum Average Subarray I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor