Sliding window

Episode 16 Minimum Size Subarray Sum

6 min · LeetCode 209 · Java

Title card of Episode 16: Minimum Size Subarray Sum

▶ This video is coming to YouTube soon.

LeetCode 209, Minimum Size Subarray Sum, solved on screen. Three examples show what counts: a short run that beats a longer one, a single number that is enough on its own, and an array that never reaches the target. Then we watch the brute force grow a sum from every start, read its code line by line, and see why it's O(n²). Finally, a variable sliding window grows on the right and shrinks from the left while its sum is still big enough, and finds the answer in one O(n) pass.

What you'll learn

  • What Minimum Size Subarray Sum asks, through three worked examples
  • The brute force: a running sum from every start, O(n²) time, O(1) space
  • The key idea: with positive numbers, growing adds and shrinking subtracts
  • The variable sliding window: O(n) time, O(1) space
  • Why this window shrinks while it's valid, the opposite of the usual template

Chapters

  1. 0:00The problem
  2. 0:16Examples
  3. 0:57Brute force, visualized
  4. 1:49Brute force: the code
  5. 2:04Brute force, line by line
  6. 2:57Sliding window: the idea
  7. 3:16Sliding window, visualized
  8. 4:05Sliding window: the code
  9. 4:22Sliding window, line by line
  10. 5:18Comparing the approaches