643. Maximum Average Subarray I
Problem Description
The problem presents an array of integers, nums
, with n
elements, and another integer, k
. The objective is to find a contiguous subarray within nums
that has a length exactly equal to k
and which has the maximum average value compared to all other possible subarrays of the same length.
Constraints that might apply to this problem, such as the range of values for n
, k
, and the individual elements in nums
, are not stated here. The answer needs to be sufficiently accurate such that a calculation error less than 10^-5
is acceptable.
Intuition
To solve this problem effectively, we can use the "sliding window" technique. The key idea behind this technique is to maintain a "window" of size k
that moves through the array, one element at a time, updating the sum of the window as it goes. By doing this, we avoid recalculating the sum for each subarray from scratch, which leads to significant time savings.
Here's the intuition step-by-step:
- First, calculate the sum of the initial window, which is the sum of the first
k
elements. - This sum is our current maximum sum (and, as it stands, the maximum average since we would divide this by
k
). - Now, slide the window by one element to the right. This means adding the element that comes after the current window and subtracting the element that is leaving the window.
- Update the maximum sum if the new window's sum is greater.
- Repeat this process of sliding the window and updating the maximum sum until we have visited all possible windows of size
k
. - Since the maximum sum will have been found by the time we've checked all windows, we can simply take the maximum sum and divide it by
k
to find the maximum average.
This approach is efficient because it calculates the necessary sum in constant time for each step of the sliding window instead of linear time if we were to add up k
elements again and again. Therefore, the overall time complexity is O(n), where n
is the number of elements in the array.
Learn more about Sliding Window patterns.
Solution Approach
The solution is implemented using the sliding window pattern as mentioned:
-
Initialization: The first step is to calculate the sum of the first
k
elements. This is done via the expressionsum(nums[:k])
. We initialize a variables
with this initial sum, and also we initialize anans
variable with the same value because, at this point, this is the maximum sum we have found, and hence the maximum average as well. -
Sliding the Window:
- The for loop with
for i in range(k, len(nums)):
begins the process of sliding the window across the array. The variablei
represents the right boundary of the current window. - As the window slides, we add the new rightmost element to our sum with
s += nums[i]
and remove the leftmost element of the previous window with- nums[i - k]
. This enables us to maintain the sum of exactlyk
elements. - After adjusting the sum, we then check if the new sum (
s
) is greater than the previously recorded maximum sum (ans
). If it is, we updateans
withans = max(ans, s)
.
- The for loop with
-
Calculating the Maximum Average:
- Once the window has slid from the start to the end of the array, the maximum sum of any subarray with length
k
will be stored inans
. - The final step is to divide
ans
byk
to find the maximum average value, which is returned as the result of the function:return ans / k
.
- Once the window has slid from the start to the end of the array, the maximum sum of any subarray with length
By following this approach, the algorithm ensures that each element is added and subtracted exactly once from the sum, leading to an efficient O(n) time complexity. No extra space is needed apart from a few variables, so the space complexity is O(1).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach. Consider the array nums = [1, 12, -5, -6, 50, 3]
and k = 4
. We want to find the contiguous subarray of length k
with the maximum average value.
Here's how the sliding window approach can be applied:
-
Initialization: First, we calculate the sum of the first
k
elements, which are1 + 12 - 5 - 6 = 2
. We sets
to2
, and alsoans
is initialized to2
. -
Sliding the Window:
- Begin the process with
i
at indexk
, or4
, which corresponds to the first number outside of our initial window,50
. - The for loop starts, i.e.,
for i in range(4, 6)
. - At
i = 4
, we addnums[4]
(which is50
) tos
, and subtractnums[4 - 4]
(which is1
, the leftmost element of the previous window). Now,s = s + 50 - 1 = 51
. - We now check if
s
is greater thanans
. Since51
is greater than2
, we updateans
to51
. - The window is now
[12, -5, -6, 50]
.
- Begin the process with
-
Continue Sliding the Window:
- Increment
i
to5
, addnums[5]
tos
, and subtractnums[5 - 4]
. Sos = 51 + 3 - 12 = 42
. - We check if
s
is greater than the currentans
. It is not (42
is less than51
), soans
remains51
. - The window is now
[-5, -6, 50, 3]
.
- Increment
-
Calculating the Maximum Average:
- We have now checked all windows of size
k
.ans
is holding the maximum sum, which is51
. - The final step is to divide
ans
(which is51
) byk
(which is4
) to find the maximum average.maximum average = ans / k = 51 / 4 = 12.75
- We have now checked all windows of size
Therefore, the subarray [12, -5, -6, 50]
returns the maximum average of 12.75
for the given array when the subarray length is 4
. This example demonstrates that we only pass through the array once, updating our sum as we go and only carrying out constant work for each element, thereby giving us an O(n) time complexity.
Solution Implementation
1from typing import List
2
3class Solution:
4 def findMaxAverage(self, nums: List[int], k: int) -> float:
5 # Initial sum of the first 'k' elements
6 current_sum = sum(nums[:k])
7 # Starting with the initial sum as the max sum
8 max_sum = current_sum
9
10 # Iterate over the list starting from the k-th element to the end
11 for i in range(k, len(nums)):
12 # Update the current sum by adding the next element and
13 # subtracting the (i-k)-th element, sliding the window forward
14 current_sum += nums[i] - nums[i - k]
15 # Update the max sum if the current sum is greater
16 max_sum = max(max_sum, current_sum)
17
18 # Calculate the maximum average by dividing the max sum by k
19 return max_sum / k
20
1class Solution {
2 public double findMaxAverage(int[] nums, int k) {
3 // Sum of the first 'k' elements.
4 int currentSum = 0;
5 for (int i = 0; i < k; ++i) {
6 currentSum += nums[i];
7 }
8
9 // Initialize the max sum as the sum of the first 'k' elements.
10 int maxSum = currentSum;
11
12 // Iterate through the array starting from the k-th element.
13 for (int i = k; i < nums.length; ++i) {
14 // Update the current window sum by adding the new element
15 // and subtracting the first element of the previous window.
16 currentSum += (nums[i] - nums[i - k]);
17
18 // Update the max sum if the current window sum is greater.
19 maxSum = Math.max(maxSum, currentSum);
20 }
21
22 // Return the maximum average, which is the max sum divided by 'k',
23 // converted to a double for precision.
24 return maxSum * 1.0 / k;
25 }
26}
27
1#include <vector>
2#include <algorithm>
3
4// Function to find the maximum average of any subarray of size k
5double findMaxAverage(std::vector<int>& nums, int k) {
6 int totalNumbers = nums.size(); // Total count of numbers in the input array
7 int maxSum = 0; // This will hold the maximum sum of any subarray of size k
8 int currentSum = 0; // This holds the sum of the current subarray size k
9
10 // Calculate the sum of the first subarray of size k
11 for (int index = 0; index < k; ++index) {
12 currentSum += nums[index];
13 }
14 maxSum = currentSum;
15
16 // Slide the window of size k through the array to find the max sum
17 // The loop starts from k since we already computed the sum for the first k elements
18 for (int index = k; index < totalNumbers; ++index) {
19 // Add the next element and remove the first element of the previous window
20 currentSum += nums[index] - nums[index - k];
21 // Update maxSum if the new currentSum is greater than maxSum
22 maxSum = std::max(maxSum, currentSum);
23 }
24
25 // The result should be the average, so divide maxSum by k
26 return static_cast<double>(maxSum) / k;
27}
28
1function findMaxAverage(nums: number[], k: number): number {
2 let totalNumbers = nums.length;
3 let maxSum = 0; // This will hold the maximum sum of any subarray of size k
4 let currentSum = 0; // This holds the sum of the current subarray of size k
5
6 // Calculate the sum of the first subarray of size k
7 for (let index = 0; index < k; index++) {
8 currentSum += nums[index];
9 }
10 maxSum = currentSum;
11
12 // Slide the window of size k through the array to find the max sum
13 // The loop starts from k since we already computed the sum for the first `k` elements
14 for (let index = k; index < totalNumbers; index++) {
15 // Add the next element and remove the first element of the previous window
16 currentSum += nums[index] - nums[index - k];
17 // Update maxSum if the new currentSum is greater than the existing maxSum
18 maxSum = Math.max(maxSum, currentSum);
19 }
20
21 // The result should be the average, so divide by k
22 return maxSum / k;
23}
24
Time and Space Complexity
The time complexity of the provided code is O(N)
where N
is the number of elements in the input list nums
. This is because the code iterates through the list once after calculating the initial sum of the first k
elements. Each iteration performs a constant number of operations: one addition, one subtraction, and one comparison.
The space complexity of the code is O(1)
because it uses a fixed amount of extra space: variables s
and ans
to keep the rolling sum and the maximum sum, respectively. The space used does not depend on the size of the input list nums
.
Learn more about how to find time and space complexity quickly using problem constraints.
You are given an array of intervals where intervals[i] = [start_i, end_i]
represent the start and end of the ith
interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.