Videos / DSA

Episode 5 of 22 · DSA, end to end

Sorting and searching: the two operations everything else is built on

Chapters

1. Three hard questions0:00
2. Scan or halve0:16
3. Twins go adjacent0:34
4. Equal keys in a block0:52
5. Rank becomes an index1:09
6. Pay once, ask often1:29
7. The hand of cards1:46
8. Merge is the trick2:02
9. Pivot and partition2:21
10. The worst case is real2:39
11. The safety net2:57
12. The floor itself3:16
13. Open the box on sort3:34
14. The depth limit3:52
15. The bad one, on purpose4:10
16. What stable means4:29
17. Two sorts compose4:46
18. What your language promises5:04
19. Open it in the middle5:22
20. One sentence invariant5:40
21. The midpoint overflows5:58
22. The loop that spins6:16
23. Search the boundary6:33
24. What falls out of it6:51
25. Turning a tap7:08
26. Monotonic or nothing7:24
27. The easy question7:43
28. Optimisation to decision8:01
29. What it costs8:19
30. The two failures8:35
31. Stop comparing8:54
32. Count, total, place9:12
33. Read the k again9:30
34. Digit by digit9:47
35. The hidden factor10:04
36. When to reach past10:22
37. The whole thing10:41

Sorting and searching: the two operations everything else is built on. Here is a drawer with ten thousand receipts in it, in no order at all. Ask it three questions. Does this one exist? Are there duplicates? Group these by month. Every answer means t

Mark as watchedSaved in this browser only.