Leetcode – Maximum Average Subarray I Solution in Python

Spread the love

Introduction

Arrays are one of the most basic and widely-used data structures in computer programming. One of the classic problems associated with arrays is finding subarrays that meet specific criteria. In this article, we are going to dive deep into solving the “Maximum Average Subarray I” problem from Leetcode. We will explore the problem in detail, walk through multiple approaches to solve it, and provide Python code for each solution.

Problem Statement (Leetcode #643)

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example:

Input: [1,12,-5,-6,50,3], k = 4

Output: 12.75

Explanation: Maximum average is (12 – 5 – 6 + 50)/4 = 51/4 = 12.75.

Note:

  • 1 <= k <= n <= 30,000.
  • Elements of the given array will be in the range [-10,000, 10,000].

Solution

1. Naive Approach

A naive approach is to calculate the average for all subarrays of length k and keep track of the maximum average encountered.

  1. Initialize a variable, max_average, to store the maximum average. Set it to negative infinity initially.
  2. Iterate through the array. For each element, calculate the average of the subarray of length k starting at that element.
  3. Update max_average if the calculated average is greater than the current maximum average.
  4. Return max_average as the result.
def find_max_average(nums, k):
    max_average = float('-inf')
    n = len(nums)
    
    for i in range(n - k + 1):
        current_sum = sum(nums[i:i+k])
        max_average = max(max_average, current_sum / k)
    
    return max_average

Time Complexity:

  • O(nk), where n is the number of elements in the array. The inner summation takes O(k) time and it is executed n times.

Space Complexity:

  • O(1), as we are using a constant amount of space.

2. Cumulative Sum Approach

We can optimize the naive approach by avoiding recalculating the sum of overlapping parts of subarrays. This can be achieved using a cumulative sum array, where each element stores the sum of elements up to that index.

  1. Construct the cumulative sum array.
  2. Initialize a variable, max_sum, to store the maximum sum of subarray of length k.
  3. Iterate through the cumulative sum array. For each element, calculate the sum of the subarray of length k starting at that element using the cumulative sum array.
  4. Update max_sum if the calculated sum is greater than the current maximum sum.
  5. Return max_sum/k as the result.
def find_max_average(nums, k):
    n = len(nums)
    cumulative_sum = [0] * (n + 1)
    
    for i in range(1, n + 1):
        cumulative_sum[i] = cumulative_sum[i - 1] + nums[i - 1]
    
    max_sum = float('-inf')
    
    for i in range(k, n + 1):
        current_sum = cumulative_sum[i] - cumulative_sum[i - k]
        max_sum = max(max_sum, current_sum)
    
    return max_sum / k

Time Complexity:

  • O(n), where n is the number of elements in the array.

Space Complexity:

  • O(n), as we are using an additional array to store the cumulative sums.

3. Sliding Window Approach

The sliding window approach is based on the observation that when moving from one subarray to the next, we are adding one element and removing one element. Therefore, we can maintain a running sum and update it as the window slides through the array.

  1. Initialize a variable, max_sum, to store the maximum sum of subarray of length k. Also, initialize a variable, window_sum, to store the sum of the current window.
  2. Iterate through the array. For each element, update the window_sum.
  3. Update max_sum if the window_sum is greater than the current maximum sum.
  4. Return max_sum/k as the result.
def find_max_average(nums, k):
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    for i in range(k, len(nums)):
        window_sum = window_sum - nums[i - k] + nums[i]
        max_sum = max(max_sum, window_sum)
        
    return max_sum / k

Time Complexity:

  • O(n), where n is the number of elements in the array.

Space Complexity:

  • O(1), as we are using a constant amount of space.

Conclusion

In this article, we explored the “Maximum Average Subarray I” problem on Leetcode and discussed three different approaches in Python: the naive approach, cumulative sum approach, and sliding window approach. The sliding window approach stands out as the most optimized solution in terms of both time and space complexity.

Leave a Reply