Two-Pointers Technique — Opposite-Ends, Same-Direction, with Java Examples

Q: Two-Pointers Technique — Opposite-Ends, Same-Direction, with Java Examples

**Two-pointer** uses two indices that traverse the array in a coordinated way, typically converging or moving in tandem, to solve problems in **O(n)** time instead of O(n²). Two main variants: **(1) Opposite ends** — `left = 0`, `right = n-1`, move them toward each other based on a condition. Used for **sorted arrays** (two-sum sorted, container with most water, palindrome check, reverse array, 3-sum). **(2) Same direction** — both pointers move forward; one (fast) leads, the other (slow) follows. Used for **in-place modification** (remove duplicates, move zeros), **linked lists** (middle, cycle detection — see Floyd's algorithm), and **streaming scans**. A **third variant**, sliding window, is sometimes classified as a two-pointer technique (both left/right move forward, like same-direction). **When to use**: (1) **sorted array** + pair/target search; (2) **palindrome**; (3) **in-place modification** where order is preserved; (4) **merge** two sorted arrays; (5) **partition** (Dutch national flag, quicksort partitioning). **Why it works**: exploits **sortedness** or **monotonicity** — moving one pointer irreversibly commits to skipping certain states, which would otherwise require nested iteration. On a **sorted array**, if `arr[left] + arr[right] > target`, decreasing `right` is safe because all pairs `(left, right_remaining)` are even smaller, so we'd never find a valid one; similarly for increasing `left` when too small. **Don't use** for: unsorted arrays without sorting first (may not find the answer), problems requiring random access patterns, or when sortedness destroys the ordering information needed. **Common complexity**: O(n) for linear passes, O(n log n) when sorting first (e.g., 3-sum).

Intermediate·6 min read·

AmazonGoogleMetaMicrosoftApple

Fast recall

Quick revision

Core answer

Two-pointer uses two indices that traverse the array in a coordinated way, typically converging or moving in tandem, to solve problems in O(n) time instead of O(n²). Two main variants: (1) Opposite ends — left = 0, right = n-1, move them toward each other based on a condition. Used for sorted arrays (two-sum sorted, container with most water, palindrome check, reverse array, 3-sum). (2) Same direction — both pointers move forward; one (fast) leads, the other (slow) follows. Used for in-place modification (remove duplicates, move zeros), linked lists (middle, cycle detection — see Floyd's algorithm), and streaming scans. A third variant, sliding window, is sometimes classified as a two-pointer technique (both left/right move forward, like same-direction). When to use: (1) sorted array + pair/target search; (2) palindrome; (3) in-place modification where order is preserved; (4) merge two sorted arrays; (5) partition (Dutch national flag, quicksort partitioning). Why it works: exploits sortedness or monotonicity — moving one pointer irreversibly commits to skipping certain states, which would otherwise require nested iteration. On a sorted array, if arr[left] + arr[right] > target, decreasing right is safe because all pairs (left, right_remaining) are even smaller, so we'd never find a valid one; similarly for increasing left when too small. Don't use for: unsorted arrays without sorting first (may not find the answer), problems requiring random access patterns, or when sortedness destroys the ordering information needed. Common complexity: O(n) for linear passes, O(n log n) when sorting first (e.g., 3-sum).

Interview Answer6 min

Two-pointer uses two indices traversing an array in a coordinated way to solve problems in O(n) instead of O(n²).

Two main variants

1. Opposite-ends (convergent)

left = 0, right = n - 1
Move toward each other based on condition
Requires sortedness or monotonicity
Examples: two-sum sorted, container with most water, palindrome, reverse array

2. Same-direction (tandem)

Both pointers move forward
Fast leads, slow follows
Used for in-place modification, linked list traversal
Examples: remove duplicates, move zeros, linked list middle

Why opposite-ends works — the monotonicity argument

Two-sum sorted example

arr[left] + arr[right] < target: moving right left gives smaller sums (already too small); must move left right
arr[left] + arr[right] > target: moving left right gives larger sums (already too large); must move right left
Each move irrevocably commits to skipping pairs — safely
Sortedness is the invariant that makes this safe

Two-sum sorted code

while (left < right) {
    sum = arr[left] + arr[right]
    if sum == target: return answer
    else if sum < target: left++
    else right--
}

O(n), O(1) space

Container with most water

Area = min(h[left], h[right]) × (right - left)
Always move the shorter side
Why? Taller side: height capped by shorter, width smaller → only decreases; moving shorter might find taller line, potentially improving

Same-direction pattern

Remove duplicates from sorted array

slow marks last unique position; fast scans
When arr[fast] != arr[slow]: slow++; arr[slow] = arr[fast]
In-place, O(n), O(1) space

Move zeros to end

slow marks next non-zero position; fast scans
Swap when arr[fast] != 0

Linked list middle

slow moves 1, fast moves 2
When fast reaches end, slow is at middle

Three-pointer extensions

3-sum

Sort, outer loop on first index
Two-pointer on remaining two indices
O(n²) overall
Skip duplicates for distinct triplets

Dutch national flag (sort 0/1/2)

low, mid, high pointers
low tracks 0-region, mid scans, high tracks 2-region
Three-way partition in O(n)
Lomuto partition uses similar idea for quicksort

Merge two sorted arrays

Two pointers i, j on the inputs
Write smaller to output, advance that pointer
O(n + m)

When to use

Sorted array + pair or triplet search → opposite-ends

Palindrome check → opposite-ends

In-place modification (preserve relative order) → same-direction

Linked list (middle, cycle, Kth from end) → same-direction

Merge sorted sequences → same-direction on each

Three-way partition → three pointers (Dutch flag)

When NOT to use

Unsorted array without sorting first

Monotonicity argument breaks
Use HashMap instead

Random access patterns

Binary search or other techniques

Problems where sortedness destroys needed info

Preserving original order matters

Common pitfalls

1. Using two pointers on unsorted array

Won't find the answer
Sort first or use HashMap

2. Infinite loop when neither pointer moves

Ensure at least one pointer advances per iteration

3. Off-by-one

Window size = right - left + 1 (inclusive)
Loop condition left < right vs left <= right

4. Duplicate handling in 3-sum

Must skip duplicates at each level for distinct triplets

5. Wrong direction for container with most water

Must move the SHORTER side

Relation to sliding window

Sliding window is a special case of same-direction two-pointer
Both left and right advance, never decrease
Windows are specifically contiguous ranges

Recommendation: Master both opposite-ends (convergent) and same-direction (tandem) variants — they handle different problem classes. For opposite-ends, always verify the array is sorted (or that monotonicity exists); otherwise the pointer-movement argument breaks. Practice the canonical problems: two-sum sorted, container with most water, 3-sum (outer loop + two-pointer), palindrome check, and Dutch national flag. For same-direction, the pattern is: slow pointer marks the next write position, fast pointer scans — this applies to remove duplicates, move zeros, and linked-list operations. For linked lists, know the fast = 2×, slow = 1× pattern for middle and cycle detection (see Floyd's algorithm). When tempted to use two-pointer on an unsorted array, ask: do I have monotonicity? If not, sort first (O(n log n)) or use a HashMap (O(n) space). The 3-sum pattern — outer loop + two-pointer inner — generalizes to 4-sum and K-sum (recursion + two-pointer at base). Beware duplicate handling: explicit skips like while (left < right && nums[left] == nums[left+1]) left++; are essential for distinct-triplet problems. The mental model: two-pointer = exploit sortedness/monotonicity to skip states; sliding window = same-direction two-pointer on contiguous ranges with stateful window. Together these patterns handle a huge fraction of array/string interview problems in O(n) time.

Interview-ready guide

Interview answer