Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Maximum Average Subarray I

Try it yourself
EasyProblemExternal link

Description

You get an integer array nums and an integer k.

Find a contiguous subarray of exactly k numbers whose average is as large as possible, and return that average.

Your answer is printed with 5 decimal places, so 12.75 shows as 12.75000.

Examples

Example 1

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

Output: 12.75000

Explanation: The best window is 12, -5, -6, 50: (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75.

Example 2

Input: nums = [5], k = 1

Output: 5.00000

Explanation: There's only one window, [5], so the answer is 5.

Constraints

  • n == nums.length
  • 1 ≤ k ≤ n ≤ 10^5
  • -10^4 ≤ nums[i] ≤ 10^4

Editorial

Brute Force

Intuition

An average of k numbers is their sum divided by k, and k is the same for every window. So the window with the largest average is the one with the largest sum.

The direct way: try every start, add up the k numbers from there, keep the largest sum, and divide it by k at the end.

Step-by-Step Explanation

Let's try every window of 4 in nums = [1, 12, -5, -6, 50, 3]:

  1. The window starting at 0: 1 + 12 − 5 − 6 = 2.
  2. The window starting at 1: 12 − 5 − 6 + 50 = 51.
  3. The window starting at 2: -5 − 6 + 50 + 3 = 42.

The largest sum is 51, so the answer is 51 / 4 = 12.75. Each window took 4 additions.

Add Up Every Window — Each step adds up one whole window from scratch. The count of additions keeps growing by k.

Algorithm

  1. Set best to minus infinity.
  2. For each start from 0 to n − k:
    • add up nums[start] through nums[start + k - 1];
    • keep the larger of that total and best.
  3. Return best / k.

Code

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        long long best = LLONG_MIN;
        for (int start = 0; start + k <= (int)nums.size(); start++) {
            long long total = 0;
            for (int i = start; i < start + k; i++) {
                total += nums[i];               // add up the whole window again
            }
            best = max(best, total);
        }
        return (double) best / k;
    }
};

class Solution:
    def findMaxAverage(self, nums: list[int], k: int) -> float:
        best = float("-inf")
        for start in range(len(nums) - k + 1):
            total = 0
            for i in range(start, start + k):
                total += nums[i]                # add up the whole window again
            best = max(best, total)
        return best / k

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        long best = Long.MIN_VALUE;
        for (int start = 0; start + k <= nums.length; start++) {
            long total = 0;
            for (int i = start; i < start + k; i++) {
                total += nums[i];               // add up the whole window again
            }
            best = Math.max(best, total);
        }
        return (double) best / k;
    }
}

var findMaxAverage = function(nums, k) {
    let best = -Infinity;
    for (let start = 0; start + k <= nums.length; start++) {
        let total = 0;
        for (let i = start; i < start + k; i++) {
            total += nums[i];                   // add up the whole window again
        }
        best = Math.max(best, total);
    }
    return best / k;
};

Complexity Analysis

Time Complexity: O(n · k)

There are n − k + 1 windows, and each costs k additions.

Space Complexity: O(1)

A few numbers.

Why This Approach Is Not Efficient

With n = 10^5 and k = 5 × 10^4 there are 50,001 windows of 50,000 numbers: about 2.5 billion additions. That's far too slow.

And most of that work is repeated. The window starting at start and the one starting at start + 1 share k − 1 numbers. Only the first number of the old window leaves, and only one new number arrives. So the next sum doesn't need to be added up again: it's the last sum, plus the number entering, minus the number leaving.

Optimal Approach - Sliding Window

Intuition

Keep a running sum of the current window. To move the window one step right, add the number that enters on the right, nums[right], and subtract the number that leaves on the left, nums[right - k]: the one k places back, just outside the new window.

The running sum is always the sum of the k numbers ending at right. That's true for the first window, because you added it up, and each step keeps it true, because the new window is the old one without its first number and with the next one.

Keep the best sum as a whole number and divide by k once, at the end. (In Java and C++, make that division a floating-point one: (double) best / k.)

Step-by-Step Explanation

Let's slide a window of 4 over nums = [1, 12, -5, -6, 50, 3]:

  1. The first window: 1 + 12 − 5 − 6 = 2.
  2. 50 enters and 1 leaves: the sum becomes 51.
  3. 3 enters and 12 leaves: the sum becomes 42.

The best sum is 51, so the answer is 51 / 4 = 12.75.

One Number In, One Number Out — The shaded window slides one step at a time: the glowing number enters, the amber one leaves, and the sum changes by exactly those two.

Algorithm

  1. Add up the first k numbers into window_sum, and set best = window_sum.
  2. For each right from k to n − 1:
    • add nums[right] and subtract nums[right - k];
    • keep the larger of window_sum and best.
  3. Return best / k.

Code

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        long long windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];               // the first window
        }
        long long best = windowSum;
        for (int right = k; right < (int)nums.size(); right++) {
            windowSum += nums[right];           // the number entering
            windowSum -= nums[right - k];       // the number leaving
            best = max(best, windowSum);
        }
        return (double) best / k;               // divide once, at the end
    }
};

class Solution:
    def findMaxAverage(self, nums: list[int], k: int) -> float:
        window_sum = sum(nums[:k])              # the first window
        best = window_sum
        for right in range(k, len(nums)):
            window_sum += nums[right]           # the number entering
            window_sum -= nums[right - k]       # the number leaving
            best = max(best, window_sum)
        return best / k                         # divide once, at the end

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        long windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];               // the first window
        }
        long best = windowSum;
        for (int right = k; right < nums.length; right++) {
            windowSum += nums[right];           // the number entering
            windowSum -= nums[right - k];       // the number leaving
            best = Math.max(best, windowSum);
        }
        return (double) best / k;               // divide once, at the end
    }
}

var findMaxAverage = function(nums, k) {
    let windowSum = 0;
    for (let i = 0; i < k; i++) {
        windowSum += nums[i];                   // the first window
    }
    let best = windowSum;
    for (let right = k; right < nums.length; right++) {
        windowSum += nums[right];               // the number entering
        windowSum -= nums[right - k];           // the number leaving
        best = Math.max(best, windowSum);
    }
    return best / k;                            // divide once, at the end
};

Complexity Analysis

Time Complexity: O(n)

k additions for the first window, then one addition and one subtraction per step.

Space Complexity: O(1)

The running sum and the best sum.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Subtracting the wrong number. window_sum += nums[right] - nums[right - k + 1]

On nums = [1, 5, 2], k = 1 it returns 1.00000; the answer is 5.00000. The number leaving is the one just outside the new window, k places back: nums[right - k]. nums[right - k + 1] is still inside, and with k = 1 it's the number that just arrived, so the sum never changes.

Starting best at 0. best = 0

On nums = [-4, -2, -6, -8], k = 2 it returns 0.00000; the answer is -3.00000. Numbers can be negative. When every window's sum is below 0, best never moves and the answer is an average no window has. Start best at the first window's sum.

Dividing two ints. return best / k;

On nums = [1, 12, -5, -6, 50, 3], k = 4 in Java it returns 12.00000; the answer is 12.75000. best / k with two ints is whole-number division: 51 / 4 is 12, and the .75 is gone before the result becomes a double. Divide as doubles: (double) best / k.

Where This Pattern Is Taught

This problem practises the fixed-size sliding window in its plainest form: one number in, one number out, and divide once at the end. It's taught in Introduction to Sliding Window.