Visualized DSA Strategies

Episode 4 Two Pointers

1 h 5 min · PHP · Quiz

Episode 4Two Pointers

▶ This video is coming to YouTube soon.

The complete guide to two pointers for coding interviews, in PHP. 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 PHP template for each, and why an in-place method takes its array by reference (&$nums); and five traps. 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 with ctype_alnum, 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, through &$nums
  • Merging from the back so nothing unread is overwritten
  • Three zones to sort 0, 1 and 2 in one pass, with one-line swaps
  • Fast and slow pointers to find a repeat, and trapping rain water from both ends

Chapters

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

Quiz: test yourself

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