Maximum Average Subarray I

Find the contiguous subarray of length k that has the maximum average value using the sliding window technique.

Sliding Window Easy LeetCode 643

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.

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.0

Interactive Visualization

1.0s
Current Sum
0
Max Sum
0
Max Average
0.00
fun findMaxAverage(nums: IntArray, k: Int): Double {    var windowSum = nums.take(k).sum()    var maxSum = windowSum        for (i in k until nums.size) {        windowSum += nums[i] - nums[i - k]        maxSum = maxOf(maxSum, windowSum)    }    return maxSum.toDouble() / k}

Status

Ready to start

Execution Log

How It Works

Key Insight

The sliding window technique allows us to find the maximum sum subarray of size k in O(n) time. Instead of recalculating the sum for each window from scratch, we maintain a running sum and update it by adding the new element entering the window and subtracting the element leaving the window.

Algorithm Steps

  1. Initialize the first window: Calculate the sum of the first k elements. This is our initial window_sum and max_sum.
  2. Slide the window: For each position from k to n-1:
    • Add the new element entering the window (nums[i])
    • Subtract the element leaving the window (nums[i-k])
    • Update max_sum if current window_sum is greater
  3. Return the result: Divide max_sum by k to get the maximum average.

Complexity Analysis

Time Complexity: O(n) We iterate through the array once
Space Complexity: O(1) Only using constant extra space