Sliding window

Episode 14 Maximum Average Subarray I

6 min · LeetCode 643 · Java

Title card of Episode 14: Maximum Average Subarray I

▶ This video is coming to YouTube soon.

LeetCode 643, Maximum Average Subarray I, solved on screen. Three examples show what's asked: the best run of k numbers in a row, an answer that's negative, and k equal to the whole array. Then we watch the brute force add up every window from scratch, read its code line by line, and see why it's O(n · k). Finally, the fixed-size sliding window from Episode 13 keeps one running sum: add the number coming in, subtract the one going out, O(n) time and O(1) space.

What you'll learn

  • What Maximum Average Subarray asks, through three worked examples
  • The brute force: add up every window, O(n · k) time, O(1) space
  • The key idea: neighbouring windows share all but two numbers
  • The fixed sliding window: one add and one subtract per step, O(n) time
  • Why comparing sums is the same as comparing averages

Chapters

  1. 0:00The problem
  2. 0:15Examples
  3. 1:25Brute force, visualized
  4. 2:26Brute force: the code
  5. 2:45Brute force, line by line
  6. 3:34Sliding window: the idea
  7. 3:56Sliding window, visualized
  8. 4:56Sliding window: the code
  9. 5:13Sliding window, line by line
  10. 6:00Comparing the approaches