Videos / DSA

Episode 9 of 22 · DSA, end to end

Prefix sums, sliding windows, and contribution counting

Chapters

1. An index, and its price0:00
2. The obvious loop, priced0:16
3. The running total0:32
4. Three numbers, compared0:49
5. The one case it loses1:05
6. What is coming, and why1:24
7. Milestones1:43
8. One subtraction1:59
9. The off by one, settled2:16
10. The grid, built2:34
11. Inclusion and exclusion2:51
12. Four reads, one number3:08
13. A highlighter3:24
14. Mark only the edges3:41
15. One pass makes it real3:57
16. The inverse pair4:14
17. The sweep line4:32
18. Four marks, not two4:49
19. A train window5:06
20. Add one, drop one5:22
21. When nobody gives you k5:39
22. The shrink condition5:56
23. Counting the pointer moves6:15
24. Where the window breaks6:33
25. Two fingers on a price list6:50
26. Closing in7:06
27. Why nothing is missed7:23
28. Same direction, two speeds7:40
29. The window, renamed7:58
30. The precondition, named8:15
31. Counting handshakes8:33
32. How many subarrays cover i8:51
33. The sum over every subarray9:07
34. The minimum owns a span9:24
35. The monotonic stack9:42
36. Ties, counted once10:01
37. The whole thing10:18

Prefix sums, sliding windows, and contribution counting. An index at the back of a book costs an afternoon to build and nothing at all to use. That is the whole of this video. Every technique here pays a fixed price once, up front, so th

Mark as watchedSaved in this browser only.