Sliding window

Episode 19 Fruit Into Baskets

6 min · LeetCode 904 · Java

Title card of Episode 19: Fruit Into Baskets

▶ This video is coming to YouTube soon.

LeetCode 904, Fruit Into Baskets, solved on screen. First the story: two baskets, one type of fruit each, picking from every tree going right. It turns into the longest subarray with at most 2 distinct values, and three examples show why the best start isn't always the first tree. Then we watch the brute force grow a run from every start with a set of types, read its code line by line, and see why it's O(n²). Finally, a variable sliding window counts each type in a HashMap, shrinks from the left when a third type gets in, and answers in one O(n) pass.

What you'll learn

  • What Fruit Into Baskets asks, and why it's 'at most 2 distinct values'
  • The brute force: a set of types from every start, O(n²) time, O(1) space
  • The key idea: a window whose HashMap holds at most 2 types
  • The variable sliding window with counts: O(n) time, O(1) space
  • Why a type leaves the map only when its count hits 0

Chapters

  1. 0:00The problem
  2. 0:26Examples
  3. 1:04Brute force, visualized
  4. 1:52Brute force: the code
  5. 2:07Brute force, line by line
  6. 2:52Sliding window: the idea
  7. 3:15Sliding window, visualized
  8. 4:05Sliding window: the code
  9. 4:20Sliding window, line by line
  10. 5:23Comparing the approaches