Visualized DSA Strategies

Episode 4 Two Pointers

1 h 5 min · Go · Quiz

Episode 4Two Pointers

▶ This video is coming to YouTube soon.

The complete guide to two pointers for coding interviews, in Go. The four shapes (both ends, read and write, two arrays, fast and slow) and the rule that says which pointer moves; what each approach costs; the Go for each shape (for as Go's while, an if with a short statement, tuple assignment to swap, ++ as a statement, slices.Sort, and slices that share their array with the caller); and five traps, one of them Go's own. Then nine types, each worked as a small problem in full: examples, the brute force animated beside the running line of code, the complete code, every line explained, and the two-pointer solution the same way.

What you'll learn

  • Why two pointers turn a double loop into one pass
  • Both ends on sorted data: too big moves r, too small moves l
  • A palindrome check that skips punctuation, in O(1) space
  • Moving the shorter wall: the container with the most water
  • 3Sum: sort, fix one number, two pointers on the rest
  • Read and write pointers to filter an array in place
  • Merging from the back so nothing unread is overwritten
  • Three zones to sort 0, 1 and 2 in one pass
  • Fast and slow pointers to find a repeat, and trapping rain water from both ends

Chapters

  1. 0:00Intro
  2. 0:24Two pointers from both ends
  3. 1:06Two pointers, same direction
  4. 1:41Four shapes of two pointers
  5. 2:26What each approach costs
  6. 3:09Two pointers in Go
  7. 4:23Five traps
  8. 5:16Nine two-pointer types
  9. 6:01Type 1 · Two numbers in a sorted array
  10. 11:56Type 2 · Reads the same both ways
  11. 19:26Type 3 · The biggest container
  12. 25:04Type 4 · Triplets that add to zero
  13. 32:10Type 5 · Remove duplicates in place
  14. 38:40Type 6 · Merge into the first array
  15. 44:57Type 7 · Sort the three colours
  16. 50:59Type 8 · The number that repeats
  17. 57:29Type 9 · How much rain is trapped
  18. 1:03:18Spot the type
  19. 1:04:03Quiz: which type?
  20. 1:04:50Recap

Quiz: test yourself

The 5 questions from the end of the episode. Pick an answer to see why it's right.