Two Pointers Technique

This is a powerful technique, primarily used on arrays or strings, that can often reduce the time complexity of a problem from O(n²) or O(n³) to O(n). It involves using two integer pointers to iterate through the data structure until they meet or satisfy a condition.

When to use it?

Look for problems involving sorted arrays or linked lists where you need to find a pair, a triplet, or a subarray that satisfies certain constraints. The key is that the data has some kind of order that you can exploit.

Common Patterns

1. Pointers from Opposite Ends

One pointer starts at the beginning (left) and the other at the end (right) of a sorted array. They move towards each other based on some condition.

Example (Two Sum on a sorted array): Find if a pair sums to a target x.
- If A[left] + A[right] == x, you've found a pair.
- If A[left] + A[right] < x, you need a larger sum, so increment left.
- If A[left] + A[right] > x, you need a smaller sum, so decrement right.

2. Pointers in the Same Direction (Fast & Slow)

Both pointers start at or near the beginning, but one (the "fast" pointer) moves ahead of the other (the "slow" pointer). This is often used to process a "window" of elements.

This pattern often evolves into the Sliding Window technique, where the pointers define a window that can grow or shrink.
- Expand: Move the right pointer to add elements to the window.
- Shrink: Move the left pointer to remove elements when a condition is violated.

Example (Longest Substring with No Repeating Characters): Use a hash set to keep track of characters in the current window [left, right]. Expand by moving right. If a character is already in the set, shrink by moving left and removing elements from the set until the duplicate is gone.

# Pseudocode for dynamic window (longest substring without repeating characters)
def lengthOfLongestSubstring(s):
  char_set = set()
  left = 0
  result = 0
  for right in range(len(s)):
    while s[right] in char_set:
      char_set.remove(s[left])
      left += 1
    char_set.add(s[right])
    result = max(result, right - left + 1)
  return result