Visualized DSA Strategies

Episode 4 Two Pointers

1 h 6 min · C++ · Quiz

Episode 4Two Pointers

▶ This video is coming to YouTube soon.

The complete guide to two pointers for coding interviews, in C++. 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 C++ for each shape (int indexes, because size() is unsigned, plus swap, resize and sort); and five traps, two of them C++'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:28Two pointers from both ends
  3. 1:10Two pointers, same direction
  4. 1:44Four shapes of two pointers
  5. 2:30What each approach costs
  6. 3:11Two pointers in C++
  7. 4:31Five traps
  8. 5:30Nine two-pointer types
  9. 6:15Type 1 · Two numbers in a sorted array
  10. 12:25Type 2 · Reads the same both ways
  11. 19:40Type 3 · The biggest container
  12. 25:37Type 4 · Triplets that add to zero
  13. 32:49Type 5 · Remove duplicates in place
  14. 39:15Type 6 · Merge into the first array
  15. 45:35Type 7 · Sort the three colours
  16. 51:46Type 8 · The number that repeats
  17. 58:09Type 9 · How much rain is trapped
  18. 1:04:14Spot the type
  19. 1:04:59Quiz: which type?
  20. 1:05:47Recap

Quiz: test yourself

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