Sliding window

Episode 18 Max Consecutive Ones III

6 min · LeetCode 1004 · Java

Title card of Episode 18: Max Consecutive Ones III

▶ This video is coming to YouTube soon.

LeetCode 1004, Max Consecutive Ones III, solved on screen. Three examples show what flipping at most k zeros means: one flip that joins two runs, k = 0 with no flips at all, and more flips than zeros. Then we watch the brute force grow a run from every start, read its code line by line, and see why it's O(n²). Finally, a variable sliding window counts the zeros inside it, shrinks from the left when there are more than k, and finds the answer in one O(n) pass.

What you'll learn

  • What Max Consecutive Ones III asks, through three worked examples
  • The brute force: grow a run from every start, O(n²) time, O(1) space
  • The key idea: the longest window with at most k zeros
  • The variable sliding window: O(n) time, O(1) space
  • Why the while loop still keeps the whole pass O(n)

Chapters

  1. 0:00The problem
  2. 0:14Examples
  3. 0:57Brute force, visualized
  4. 1:46Brute force: the code
  5. 2:02Brute force, line by line
  6. 2:49Sliding window: the idea
  7. 3:13Sliding window, visualized
  8. 4:02Sliding window: the code
  9. 4:17Sliding window, line by line
  10. 5:11Comparing the approaches