Leetcode 643. Maximum Average Subarray I

Question

Question - 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. Test Case- nums = [1,12,-5,-6,50,3], k = 4

The answer I am getting is 12.00000 instead of 12.75000. This happens every time there a max value that is not completely divisible by k. Can someone tell me why?

Here's my solution:

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        double s = 0;
        double max = Integer.MIN_VALUE;

        if (n == 1){
            max = Double.valueOf(nums[0]);
        } 
        else {
            for (int i = 0; i <= n-k; i++){
                for(int j = i; j < i+k-1; j++){
                    s += nums[j]; 
                    max = Math.max(max, s);
                }
            }
        }
        return max/k;
    }
}

Answer 1

Fixed the solution

Here are the issues with the provided solution:

1. The inner loop's iteration condition is incorrect. It should be j <= i + k - 1 instead of j < i + k - 1. The original condition causes the loop to terminate one index before the desired subarray length.

2. The accumulation of the sum (s) is not reset correctly within each iteration of the outer loop. Currently, the sum keeps accumulating from the previous subarray, leading to incorrect results. The s variable should be reset to 0 at the beginning of each outer loop iteration.

3. The maximum value (max) is not being calculated correctly. The current implementation compares the cumulative sum (s) with the maximum value (max) within the inner loop, which results in incorrect values. Instead, the maximum value should be updated after each subarray's sum is calculated, not within the inner loop.

Here's the corrected code:

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        double max = Integer.MIN_VALUE;

        if (n == 1) {
            max = Double.valueOf(nums[0]);
        } else {
            for (int i = 0; i <= n - k; i++) {
                double s = 0;
                for (int j = i; j <= i + k - 1; j++) {
                    s += nums[j];
                }
                max = Math.max(max, s);
            }
        }
        return max / k;
    }
}

With these corrections, the solution should correctly calculate and return the maximum average value.

Optimization

Due to the time complexity issue of the previous code, which was O(n^2) and resulted in exceeding the time limit, it was necessary to optimize it using the sliding window technique to achieve a time complexity of O(n). Here's the optimized code:

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        int maxSubSum = Integer.MIN_VALUE;
        int currentSubSum = 0;
        int l = 0;
        int r = 0;
        while (l + k - 1 < n) {
            while (r - l + 1 <= k) {
                currentSubSum += nums[r];
                r++;
            }
            maxSubSum = Math.max(maxSubSum, currentSubSum);
            currentSubSum -= nums[l];
            l++;
        }
        return (double) maxSubSum / k;
    }
}

The explanation of the optimized solution

Here's the explanation of the optimized solution with a time complexity of O(n):

The optimized solution uses a sliding window technique to find the maximum subarray sum. Here's how it works:

1. Initialize the variables maxSubSum and currentSubSum to track the maximum subarray sum and the sum of the current subarray, respectively. Set maxSubSum to Integer.MIN_VALUE to ensure correct initialization.

2. Initialize two pointers, l and r, representing the left and right boundaries of the subarray.

3. While the right boundary r is within the array bounds and while the subarray length (r - l + 1) is less than or equal to k, perform the following steps:

   • Add the element at the right boundary (nums[r]) to the currentSubSum.
   • Increment the right boundary r.

4. Once the subarray length exceeds k, update the maxSubSum by comparing it with the currentSubSum. Take the maximum of the two values.

5. Subtract the element at the left boundary (nums[l]) from the currentSubSum and increment the left boundary l.

6. Repeat steps 3 to 5 until the left boundary l reaches the end of the array.

7. Finally, return the maximum subarray sum (maxSubSum) divided by k as the maximum average value.

This optimized solution avoids unnecessary recalculations by using a sliding window approach, reducing the time complexity to O(n).

Answer 2

You need move

max = Math.max(max, s);

out of the inner loop, so that it takes the max sum of the entire window of k numbers. Putting it inside will fail if windows have any trailing negative values.

Also, reset s to 0 with each window check.

Final code will be

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        double s = 0;
        double max = Integer.MIN_VALUE;

        if (n == 1){
            max = Double.valueOf(nums[0]);
        } else{
            for(int i = 0; i < n-k; i++){
                s = 0;
                for(int j = i; j < i+k; j++){
                    s += nums[j]; 
                }
                max = Math.max(max, s);
            }
        }

        return max/k;
    }
}

This code is passing LeetCode testcases.