When to Use Two Pointers

The Two Pointers pattern is one of the simplest yet most powerful tools for array and string problems. It often turns an O(n²) brute‑force into an O(n) or O(n log n) solution.

If you find yourself scanning a sequence while comparing pairs of positions, Two Pointers should be on your shortlist.

Core Idea

Instead of using nested loops like:

JavaCopy
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        // compare or update using (i, j)
    }
}

you maintain two indices:

• i and j move monotonically (never go backwards).
• At each step, you decide which pointer to move based on the current values.

This eliminates redundant work and keeps the total number of pointer moves O(n) (or O(n log n) when combined with sorting).

Common Sub‑Patterns

1. Same‑Direction Pointers

Both pointers move from left to right:

• Remove duplicates from sorted array.
• Move zeros to the end / partition by condition.
• Merge two sorted arrays.

A typical template:

JavaCopy
int i = 0, j = 0;
while (j < n) {
    // Maintain some invariant on prefix [0..i)
    // Use a[j] to update that invariant
    if (/* a[j] should be kept */) {
        a[i] = a[j];
        i++;
    }
    j++;
}
// Result is in prefix [0..i)

2. Opposite‑Direction Pointers

One pointer starts at the left, the other at the right:

• Two‑sum in a sorted array.
• Valid palindrome after ignoring non‑alphanumerics.
• Trapping rain water (with some additional state).

Template for “find pair with condition”:

JavaCopy
int i = 0, j = n - 1;
while (i < j) {
    long sum = a[i] + a[j];
    if (sum == target) {
        // found answer
        break;
    } else if (sum < target) {
        i++; // need a larger sum
    } else {
        j--; // need a smaller sum
    }
}

Key: the array must be sorted (or have some monotonic structure) so that moving i / j changes the condition in a predictable way.

3. Fast & Slow Pointers (Cycle / Middle)

One pointer moves faster than the other:

• Detect cycle in linked list (Floyd’s algorithm).
• Find middle node of a list.
• Partitioning based on relative speeds.

Example: find middle node of singly linked list:

JavaCopy
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
// slow points to the middle

Two Pointers vs Sliding Window

Two Pointers and Sliding Window look similar but are not the same:

Pattern	Focus	Always maintains a window?
Two Pointers	Relationship of two indices	Not necessarily
Sliding Window	A contiguous range with state	Yes

• If you are maintaining a contiguous subarray / substring with some running state (sum, counts, etc.), think Sliding Window.
• If you only care about how i and j move relative to each other (e.g. sum, ordering, distance) and not about all interior elements, plain Two Pointers is enough.

Typical Problems

Here are some classic problems where Two Pointers shines:

• Remove duplicates from sorted array.
• Two sum in sorted array.
• Merge sorted arrays / lists.
• Move zeros to the end while keeping order.
• Check if a string is a palindrome under some rules.

For each new problem, ask:

1. Can I sort the array (if not already sorted)?
2. Does moving i right make some quantity increase while moving j left makes it decrease (or vice versa)?
3. Can I decide locally which pointer to move based on the current values?

If yes, it’s a strong Two Pointers candidate.

Common Pitfalls

• Forgetting to sort when needed
  • Many Two Pointers tricks rely on sorted input; if you skip sorting, reasoning breaks.
• Infinite loops
  • Each branch in the loop must move at least one pointer.
• Incorrect invariants
  • Before writing code, state out loud what condition should always hold for i and j.

When debugging, trace a small example by hand and write down (i, j, state) at each step. If a pointer stops moving or oscillates improperly, your move rules need adjustment.

When to Reach for Two Pointers

Use this checklist:

1. The input is a sequence (array / string / linked list).
2. You care about pairs of positions or partitioning the array.
3. There is a monotonic property (sorted, or can be sorted) that lets you reason about which side to move.

If the answer is yes, starting from a Two Pointers template is usually faster than starting from scratch.