Sliding Window

LeetCode 643

LeetCode #643Difficulty: EasyNeetCode 150

LeetCode 643: Maximum Average Subarray I

LeetCode

Find a contiguous subarray whose length is equal to k that has the maximum average value in O(N) linear time.

Problem Description

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.

Examples:
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75
Constraints:
  • 1 <= k <= nums.length <= 10^5

Core Mental Model

Adjacent windows share k-1 elements: WindowSum(i) = WindowSum(i-1) - nums[i-k] + nums[i]. Slide with 1 subtraction and 1 addition in O(1).

Formal Loop Invariant

Invariant: windowSum represents nums[i-k+1 ... i].

Key Architectural Takeaway:

Update only boundary elements instead of recomputing full range.

Asymptotic Complexity Analysis

Time ComplexityO(N) Linear scan.
Space ComplexityO(1) Constant memory.

Bottleneck: Reduces compute by factor of K.

Edge Cases & Screener Traps

  • k == nums.length
  • Negative numbers