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

  2. Input: nums = [5,5,5,5], k = 2 Output: 5.0

Constraints:

Clarifying Questions

  1. Q: Can the length of nums be less than k?

    A: No, the problem constraints guarantee that 1 <= k <= n.

  2. Q: Can the elements be negative?

    A: Yes, elements can be between -10^4 and 10^4.

  3. Q: How precise does the output value need to be?

    A: The calculation error should be less than 10^-5.

Strategy

To solve the problem efficiently, we will use the sliding window technique. The process involves:

  1. Initially calculating the sum of the first k elements.
  2. Using a sliding window to move through the array while updating the sum by adding the next element and subtracting the element that’s left behind.
  3. Keep track of the maximum sum encountered during these steps.
  4. Divide the maximum sum by k to get the maximum average.

Code

Here is the Java implementation of the described strategy:

public class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double maxSum = 0;
        double currentSum = 0;
        
        // Calculate the initial sum of the first k elements
        for (int i = 0; i < k; i++) {
            currentSum += nums[i];
        }
        
        maxSum = currentSum;
        
        // Slide the window from k to n
        for (int i = k; i < nums.length; i++) {
            currentSum += nums[i] - nums[i - k];
            maxSum = Math.max(maxSum, currentSum);
        }
        
        // Return the maximum average
        return maxSum / k;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {1, 12, -5, -6, 50, 3};
        int k1 = 4;
        System.out.println(solution.findMaxAverage(nums1, k1)); // Expected Output: 12.75
        
        int[] nums2 = {5, 5, 5, 5};
        int k2 = 2;
        System.out.println(solution.findMaxAverage(nums2, k2)); // Expected Output: 5.0
    }
}

Time Complexity

The time complexity for this solution is (O(n)), where (n) is the number of elements in the nums array. This is because we need to iterate through the array a single time to compute the sum of elements in the sliding window.

The space complexity is (O(1)) since we only need a few variables to keep track of the sum, maximum sum, and the average. Thus, this solution is optimal for the constraints provided in the problem statement.

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