Two Pointers Technique

Summary: The two pointers technique is a powerful pattern for solving array and string problems efficiently. By using two indices that move independently, you can often reduce time complexity from O(n²) to O(n).

What is the Two Pointers Technique?

Two pointers is a general approach where you use two indices (or iterators) to traverse a data structure, usually an array or string. The pointers can move in the same or opposite directions, or even on different arrays.

When to use: When you need to search for pairs, subarrays, substrings, or perform in-place modifications efficiently.

🧩 Common Two Pointers Patterns

Opposite Direction Pointers (Left + Right)
- When: Array/string is sorted, looking for a pair that satisfies a condition.
- Example: Two Sum in Sorted Array, Container With Most Water, Valid Palindrome, Reverse a string/linked list.
- Template:
```
int l = 0, r = n - 1;
while (l < r) {
    // Check condition
    if (arr[l] + arr[r] == target) return true;
    if (arr[l] + arr[r] < target) l++;
    else r--;
}
```
Sliding Window (Two Pointers in Same Direction)
- When: You need a window that grows/shrinks (e.g., substring/subarray problems).
- Example: Largest substring without repeating characters, Minimum window substring, Subarray sum constraints.
- Template:
```
int l = 0;
for (int r = 0; r < n; r++) {
    // expand window by including arr[r]
    while (window violates condition) {
        // shrink from left
        l++;
    }
    // update answer
}
```
- More on Sliding Window →

Fast & Slow Pointers (Tortoise & Hare)

When: Detecting cycles, finding the middle, removing Nth node from end, etc.

Template:

ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
}

Same Direction but With Gap / K-distance Pointers

When: Removing duplicates, merging sorted arrays, comparing substrings, k-distance apart comparisons.

Template:

int i = 0;
for (int j = 0; j < n; j++) {
    if (arr[j] != arr[i]) {
        i++;
        arr[i] = arr[j];
    }
}

Two Pointers on Two Arrays

When: Merging sorted arrays, intersection, comparing two sequences.

Template:

int i = 0, j = 0;
while (i < n && j < m) {
    if (a[i] == b[j]) { ... i++; j++; }
    else if (a[i] < b[j]) i++;
    else j++;
}

🚩 Key Takeaways

Two pointers is a versatile pattern for many array and string problems.
It helps reduce time and space complexity.
Patterns include opposite direction, sliding window, fast/slow, k-gap, and two arrays.
Mastering these unlocks efficient solutions to many classic problems.