643. Maximum Average Subarray I

EasyArraySliding Window
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Solution Approach

The solution is implemented using the sliding window pattern as mentioned:

  1. Initialization: The first step is to calculate the sum of the first k elements. This is done via the expression sum(nums[:k]). We initialize a variable s with this initial sum, and also we initialize an ans variable with the same value because, at this point, this is the maximum sum we have found, and hence the maximum average as well.

  2. 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 variable i 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 exactly k 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 update ans with ans = max(ans, s).

  3. 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 in ans.
    • The final step is to divide ans by k to find the maximum average value, which is returned as the result of the function: return ans / k.

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).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example 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:

  1. Initialization: First, we calculate the sum of the first k elements, which are 1 + 12 - 5 - 6 = 2. We set s to 2, and also ans is initialized to 2.

  2. Sliding the Window:

    • Begin the process with i at index k, or 4, 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 add nums[4] (which is 50) to s, and subtract nums[4 - 4] (which is 1, the leftmost element of the previous window). Now, s = s + 50 - 1 = 51.
    • We now check if s is greater than ans. Since 51 is greater than 2, we update ans to 51.
    • The window is now [12, -5, -6, 50].

  3. Continue Sliding the Window:

    • Increment i to 5, add nums[5] to s, and subtract nums[5 - 4]. So s = 51 + 3 - 12 = 42.
    • We check if s is greater than the current ans. It is not (42 is less than 51), so ans remains 51.
    • The window is now [-5, -6, 50, 3].

  4. Calculating the Maximum Average:

    • We have now checked all windows of size k. ans is holding the maximum sum, which is 51.
    • The final step is to divide ans (which is 51) by k (which is 4) to find the maximum average. maximum average = ans / k = 51 / 4 = 12.75

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
Not Sure What to Study? Take the 2-min Quiz：

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

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.

Fast Track Your Learning with Our Quick Skills Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Recommended Readings

Sliding Window Maximum

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫