two pointers technique

Topics

• algorithmic paradigm

This is a classic technique where you iterate through a data-structure (commonly arrays) using two indices. These “pointers” traverse the data structure, typically in opposite directions, in the same direction, or at varying paces depending on the problem (e.g. find pairs). It’s effective for reducing time complexity from $O(n^2)$ to $O(n)$ or $O(n\log n)$. Note that it’s often confusedwith a related technique named sliding window

When to use?

Problems that involve finding pairs, subarrays, or segments satisfying certain conditions. It can be used in conjunction with other tricks such as binary search.

• Sorted Arrays/Linked Lists: For problems involving pairs, triplets, or subarrays (e.g., two-sum, 3 Sum, merging sorted arrays)
• In-Place Operations: Removing duplicates, partitioning arrays (e.g., dutch national flag algorithm)
• Cycle Detection: floyd’s cycle finding algorithm for linked list cycles.
• Greedy Scenarios: Interval scheduling, minimizing/maximizing values (e.g., container with most water)

Step-by-Step Framework

• Identify the Problem Type:
  • Look for keywords like “sorted,” “subarray,” “pair,” or “sequence.”
  • Check if brute-force approaches involve nested loops (indicating potential for optimization).
• Initialize Pointers:
  • Opposite Ends: For sorted arrays (e.g., two-sum).
  • Same start + different speeds: slow and fast pointers (e.g., remove duplicates, cycle detection).
  • Different sequences: e.g. merging sorted arrays, intersection of two linked lists
• Define Movement Conditions:
  • Move pointers based on comparisons (e.g., sum of elements vs. target).
• Termination Condition:
  • Typically when pointers cross (opposite ends) or the fast pointer reaches the end (slow/fast).

Related

• sliding window