Videos / DSA

Episode 13 of 22 · DSA, end to end

Two pointers: one pass instead of two loops

Chapters

1. Two loops, or one pass0:00
2. What a pointer is here0:15
3. The order you lean on0:32
4. Monotonicity0:48
5. What breaks without it1:04
6. The check before you write1:22
7. From both ends1:37
8. The pair sum, traced1:54
9. Why dropping one is safe2:13
10. A row or a column at a time2:28
11. Water between walls2:44
12. Move the shorter wall3:01
13. Both from one end3:16
14. Read pointer, write pointer3:31
15. Traced, slot by slot3:49
16. The invariant4:05
17. Partitioning, in one sweep4:24
18. The sliding window4:41
19. Two runners on a track4:59
20. Tortoise and hare5:15
21. The gap closes5:30
22. And on a plain array5:46
23. Back to the head6:04
24. Mu and lambda6:19
25. Two sorted piles6:36
26. The merge loop6:51
27. Six outputs, five compares7:08
28. Merge from the back7:26
29. One character7:42
30. K lists, one heap7:59
31. The uncomfortable question8:18
32. State the invariant8:35
33. One step8:51
34. And it ends9:08
35. The same skeleton9:25
36. When it is wrong9:40
37. The whole thing9:56

Two pointers: one pass instead of two loops. Here is a sorted row of numbers, and a question. Which two of them add to sixteen? The obvious answer is two nested loops, checking every pair. That is order n squared. There is a

Mark as watchedSaved in this browser only.