643. Maximum Average Subarray I
Maximum Average Subarray I (LeetCode 643) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Fixed Size (Subarray Calculation) subpattern.
How to solve Maximum Average Subarray I
Maximum Average Subarray I is a Fixed Size Sliding Window problem, part of Sliding Window. Learn fixed-size sliding window for subarray calculations like maximum average, moving average, and k-size subarray problems.
Work towards the solution in these steps:
- Consider how you might efficiently examine all contiguous subarrays of size k in the array.
- Think about maintaining a running sum of the current subarray to avoid recalculating sums from scratch.
- How can you update the sum when you move the window one element forward?
The reference solution runs in O(n) time and O(1) space.
The Maximum Average Subarray I solution and editorial walks through the full approach with reference code.
Problem statement
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
Topics and companies
Topics: Array, Sliding Window.
Reported in interviews at Amazon.
How to practise Maximum Average Subarray I on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Maximum Average Subarray I in the code editor, or read the Maximum Average Subarray I editorial for a worked solution with its approach and complexity analysis.
Where Maximum Average Subarray I sits in the DSA pattern sheet
Problems related to Maximum Average Subarray I
Other problems that use the same Fixed Size (Subarray Calculation) and Sliding Window techniques:
- Calculate Compressed Mean — Easy, same subpattern
- Find the Power of K-Size Subarrays I — Medium, same subpattern
- Find X-Sum of All K-Long Subarrays I — Easy, same subpattern
- Moving Average from Data Stream — Easy, same subpattern
- Contains Duplicate II — Easy, same pattern
- Continuous Subarrays — Medium, same pattern
Maximum Average Subarray I FAQ
What is the LeetCode number of Maximum Average Subarray I?
Maximum Average Subarray I is LeetCode problem 643, rated Easy.
What pattern is used to solve Maximum Average Subarray I?
Maximum Average Subarray I is a Fixed Size Sliding Window problem. It belongs to the Sliding Window pattern, in the Fixed Size (Subarray Calculation) subpattern.
What is the time complexity of Maximum Average Subarray I?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Maximum Average Subarray I?
Maximum Average Subarray I has been reported in interviews at Amazon.