Logo

Kode$word

Maximum Average Subarray I — Efficient Solution Using Sliding Window (LeetCode 643)

Maximum Average Subarray I — Efficient Solution Using Sliding Window (LeetCode 643)

How to optimize subarray average calculation from brute force to an O(n) sliding window approach

7 views
0
0
LeetCodeSliding WindowEasy
Github icon

Introduction

LeetCode Problem 643: Maximum Average Subarray I is a classic problem that tests understanding of arrays and the sliding window technique.

The task is simple in description but requires optimization to work efficiently for large inputs.

We are given:

  1. An integer array nums
  2. An integer k

We must find a contiguous subarray of length k that has the maximum average value, and return that average.

If you want to try solving the problem yourself before reading further, you can attempt it here:

👉 Try the problem on LeetCode:

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


Problem Understanding

A brute-force solution would compute the sum for every subarray of length k and track the maximum average. However, recalculating sums repeatedly results in O(n × k) time complexity, which becomes inefficient for large arrays.

Instead, we can use the sliding window technique to optimize the process.

Key Idea: Sliding Window

Instead of recomputing sums:

  1. Compute the sum of the first window of size k.
  2. Slide the window forward by:
  3. Adding the next element
  4. Removing the element leaving the window
  5. Update the maximum average at each step.

This reduces time complexity to O(n).

Approach

  1. Maintain two pointers representing the window.
  2. Keep adding elements until window size becomes k.
  3. Compute average and update maximum.
  4. Slide the window by removing the left element.
  5. Continue until the end of the array.


Implementation (Java)

class Solution {
public double findMaxAverage(int[] nums, int k) {
double ans = Integer.MIN_VALUE;
int i = 0;
int j = 0;
int sum = 0;

while (j < nums.length) {
sum += nums[j];

if (j - i + 1 < k) {
j++;
} else {
ans = Math.max(ans, (double) sum / k);
sum -= nums[i];
i++;
j++;
}
}

return ans;
}
}

Dry Run Example

Input:

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

Windows examined:

[1,12,-5,-6] → avg = 0.5
[12,-5,-6,50] → avg = 12.75 (maximum)
[-5,-6,50,3] → avg = 10.5

Maximum average = 12.75

Complexity Analysis

Time Complexity: O(n)

Each element enters and leaves the window once.

Space Complexity: O(1)

No extra space is used apart from variables.

Edge Cases Considered

  1. Single element array (k = 1)
  2. All negative numbers
  3. Large input size
  4. Large positive or negative values


Why Sliding Window Matters

Sliding window is a crucial technique used in many interview problems:

  1. Subarray sum problems
  2. Longest substring problems
  3. Fixed or variable window size optimizations

Mastering this pattern greatly improves coding interview performance.


Conclusion

This problem demonstrates how recognizing patterns like sliding window can transform a slow brute-force solution into an efficient one.

If you are preparing for coding interviews, mastering sliding window problems is essential since they appear frequently.

Related Articles

Count Subarrays of Size K with Average ≥ Threshold — Sliding Window Solution (LeetCode 1343)

Count Subarrays of Size K with Average ≥ Threshold — Sliding Window Solution (LeetCode 1343)

Efficiently counting qualifying subarrays using an O(n) sliding window approach

Read Article
Left and Right Sum Differences

Left and Right Sum Differences

LeetCode 2574 Easy

Read Article
Maximum Product Subarray

Maximum Product Subarray

LeetCode Question 152 Medium

Read Article
Intersection of Two Arrays

Intersection of Two Arrays

LeetCode Question 349

Read Article
Ai Assistant Kas