algoadvance

Leetcode 643. Maximum Average Subarray I

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.75
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Example 2:

Input: nums = [5], k = 1
Output: 5.00000

Clarifying Questions

  1. Q: Can n be smaller than k? A: No, n will always be greater than or equal to k.

  2. Q: Can the array have negative numbers? A: Yes, the array can have negative numbers.

  3. Q: Is the array always non-empty? A: Yes, the array is non-empty, and k is a valid number.

  4. Q: How large can n and k be? A: Typically, constraints are given such that both n and k will be within reasonable limits for performance in an O(n) approach.

Strategy

To find the subarray of length k with the maximum average, follow these steps:

  1. Initial Sum Calculation: Compute the sum of the first k elements. This will be the initial sum and average.
  2. Sliding Window Technique: Use a sliding window to traverse through the array:
    • For each position from k to n - 1:
      • Subtract the element that is sliding out of the window (i.e., nums[i - k]).
      • Add the element that is sliding into the window (i.e., nums[i]).
      • Update the maximum sum if the new sum is greater than the current maximum sum.
  3. Compute Average: Divide the maximum sum by k to get the maximum average.

Code

#include <vector>
#include <limits>

using namespace std;

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int n = nums.size();
        int current_sum = 0;
        
        // Compute the sum of the first k elements
        for (int i = 0; i < k; ++i) {
            current_sum += nums[i];
        }
        
        int max_sum = current_sum;
        
        // Sliding window to find the maximum sum of k consecutive elements
        for (int i = k; i < n; ++i) {
            current_sum += nums[i] - nums[i - k];
            if (current_sum > max_sum) {
                max_sum = current_sum;
            }
        }
        
        // Calculate the maximum average
        return (double)max_sum / k;
    }
};

Time Complexity

Thus, the overall time complexity is O(n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI