Solving Problems with the Two-Pointers Technique

type

status

date

summary

When two pointers shine

You can order the search space: numeric sort, lexicographic order, or indices along a line.

You’re answering a range/contiguity question (subarray, substring).

There’s a monotone decision: as one pointer moves, feasibility only gets easier/harder.

You must process two streams in sorted order (merge/intersection).

You need relative position (e.g., “middle”, “cycle”) on a linked structure.

Overview

Pattern Name	Pointers Move	Typical Application	Key Characteristic
Opposing Pointers	`left` → `right` ←	Two Sum (Sorted), Trapping Rain Water, In-place Reversal (Arrays/Strings).	The search space is systematically narrowed until the pointers meet or the condition is met.
Fast/Slow Pointers	`slow` → `fast` → →	Linked list cycle detection (Floyd's Algorithm), finding the middle of a list, in-place removal of duplicates.	Pointers move at different speeds within a single structure to find relationships or specific points.
Sliding Window	`left` → `right` →	Minimum/Maximum subarray/substring problems (e.g., longest substring with K distinct characters).	The window size varies (or is fixed) as both pointers move forward; the time complexity is O(N) because each element is visited at most twice.
Two Pointers, Two Inputs	`i` → (in Arr1) `j` → (in Arr2)	Merging two sorted lists or arrays (like in Merge Sort), finding the intersection or union of two sorted sets.	Pointers advance independently based on comparisons between the elements of the two distinct inputs.

1. Opposing Pointers (Two-Pointer Convergence)

This is typically used in sorted arrays to find pairs, triples, or a target value by narrowing the search space.

Pointers start at opposite ends and move toward each other (converge).

Template (pair sum on sorted)

Dedup for k-sum

After finding a match, skip duplicates to avoid O(n²) output explosion:

Classic twists

3Sum/4Sum: Sort + fix one/two anchors, then two-pointer on the rest.

Trapping Rain Water: Always move the lower side; the trapped height at that side is bounded by its side max—no right info needed when left max < right max.

2. Sliding Window (Homodirectional Pointers)

The pointers move in the same direction and define a contiguous subarray or substring (the "window").

This is perfect for range problems like finding the longest subarray that satisfies a condition.

Each element is added at most once (when right advances) and removed at most once (when left advances).

Since the pointers never cross and advance at most once each, the complexity remains O(n).

1) Numeric window (sum/length constraints)

This involves maintaining a window over numeric values where we care about the sum or the length of the subarray/window.

Example: Length of the longest subarray whose sum is at most S

2) Frequency window (strings / distinct counts)

Problems involving ‘at most K distinct elements’ serve as fundamental building blocks. Many ‘exactly K distinct elements’ problems reduce to at_most(K) - at_most(K-1).

A hash map or dictionary is often used to maintain character frequencies inside the window.

Example: Count substrings with at most K distinct characters

3) Fixed-size windows

The window size remains fixed throughout the iteration. Each step moves the window exactly one position to the right.

Example: Moving average over k elements

3. Fast and Slow Pointers

Also known as the Runner technique or Tortoise and Hare technique. This pattern uses two pointers moving at different speeds within a single list or array.

It is valued for its simplicity, efficiency (often O(n) time with O(1) space), and its wide applicability in both linked lists and array problems. For example:

Linked lists: cycle detection (Floyd), cycle length, cycle entry, middle node.

Arrays-as-graph: find duplicate number, In-place removal of duplicates in sorted array.

4. Two Pointers, Two Inputs

Pointers move independently across two separate iterable objects like sets/lists.

This is commonly used when both inputs are sorted (or streams arriving in sorted order), and we need merge, intersection/union, or to diff the two inputs.

Example: Merge

Selecting the Right Pattern

Need a contiguous range on one array/string? → Sliding Window.

Two sorted inputs to combine/compare? → Two-Inputs/Merge.

One sorted input, search sum/diff/pairs? → Opposing Pointers.

Linked structure / cycle / middle? → Fast & Slow.

Water/area with left-right bounds? → Opposing, always move the smaller side.

If none apply cleanly, ask: can I sort once to unlock (1) or (3)? Can I encode it as a monotone window?

Tips

Duplicates: Always decide semantics (count-all vs unique) before coding; skip duplicates proactively.

Window correctness: Update the window’s state (sum/freq) precisely on both expand and shrink.

Stability & indices: If sorting breaks original indices, sort pairs (value, index).

Final Thought

The two-pointer technique simplifies complex, nested-loop problems into elegant, linear-time solutions with minimal memory overhead. By understanding when and how to apply different patterns—such as converging from opposite ends, using sliding windows, or employing fast and slow pointer dynamics—we can leverage order, locality, and relative position to solve problems intuitively and efficiently.