643. Maximum Average Subarray I – Solution [Brute-Force to Best]

Here’s the question link on LeetCode 643. Maximum Average Subarray I:

https://leetcode.com/problems/maximum-average-subarray-i/description

Brute Force O(n × k)

The straightforward approach is to calculate the sum of every possible subarray of size k.

For every starting index, I can iterate over the next k elements, calculate their sum, and update the maximum average.

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int n = nums.size();
        double ans = -1e9;

        for(int i = 0; i <= n - k; i++) {
            int sum = 0;

            for(int j = i; j < i + k; j++) {
                sum += nums[j];
            }

            ans = max(ans, (double)sum / k);
        }

        return ans;
    }
};
643. Maximum Average Subarray I Brute Force Solution

Optimal O(n) – Sliding Window

Wait, we’re calculating almost the same thing again and again.

Think about two consecutive windows:

[1, 12, -5, -6]  // sum = 2

[12, -5, -6, 50] // sum = 51

Notice something? Both windows share k-1 elements!

The only difference is:

  • The first element leaves the window.
  • A new element enters the window.

So instead of calculating the entire sum again, we can simply subtract the element leaving and add the new element.

This is called Sliding Window.

Also, since every window has exactly k elements, maximizing the average is the same as maximizing the sum. We only need to divide by k at the end.

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int n = nums.size();

        int sum = 0;

        // Calculate the first window
        for(int i = 0; i < k; i++) {
            sum += nums[i];
        }

        int maxSum = sum;

        // Slide the window
        for(int i = k; i < n; i++) {
            sum += nums[i] - nums[i-k];

            maxSum = max(maxSum, sum);
        }

        return (double)maxSum / k;
    }
};
643. Maximum Average Subarray I Optimal Sliding window Solution

That’s it; see you in the next one.

643. Maximum Average Subarray I 643. Maximum Average Subarray I 643. Maximum Average Subarray I

Leave a Reply