Two-pointer problems

As the name suggests, this is problems whose efficient solution involves tracking two pointers. It comes in two flavors: “fast-and-slow,” and “wide-to-narrow”

Pointer-chasing (“fast-and-slow”)

Typically in graph structures, like linked lists Can be used to, eg, detect cycles

Rivaling pointers (“wide-to-narrow”)

• Start with a pointer at each end, make an adjustment to one at a time, and stop when they meet
• Helpful for situations where you’d otherwise need to do an search
  • When applicable, can get worst-case time complexity from to
• For many applications, you need to sort first to get this to work