Last Minute Notes
  • Github
  • Docs
  • Learn
    @sayanstwt
Lessons
0/15 done
  • Sliding Window
  • Two Pointers
  • Prefix Sum & Hash Map
  • Cyclic Sort
  • Merge Intervals
  • Monotonic Stack
Learn/Data Structures & Algorithms/Arrays & Strings

Sliding Window

8 min Beginner 9 steps

Grow and shrink a window instead of rescanning every subarray.

Window
0..2
Additions
3n × k
Sum
8
sum 8012345215132
current done skipped
In this lessonStep 1 of 9
  1. The problem
  2. Slide
  3. Fixed run
  4. Answer
  5. Variable
  6. Shrink
  7. Full run
  8. Shortest
  9. Recap
Step 1 / 9problem

Brute force rescans every window

Find the largest sum of any 3 consecutive numbers in [2, 1, 5, 1, 3, 2].

The obvious way starts at every index and adds up the next k numbers. Neighbouring windows share k - 1 numbers, yet each one is added again from scratch.

Key idea

If an answer is about a contiguous subarray or substring and brute force is O(n²) or O(n·k), think sliding window.

←→ step·R replay·Space pause

You'll learn

  • Spot problems about contiguous subarrays
  • Run a fixed size window in O(n)
  • Grow and shrink a variable window
  • Flip the loop to find the shortest window
Read the full notesArrays and Linked Lists, 2