Two Pointers

Concept

The Two Pointers pattern uses two index variables that move through the array (or string) — either toward each other (opposite direction) or in the same direction (fast/slow pointers).

It eliminates the need for nested loops, reducing O(n²) brute-force solutions to O(n).

When to Use

The array/string is sorted (or sorting it first is allowed)
You're looking for pairs or triplets that satisfy a condition
You need to partition or remove elements in-place
The problem mentions "two numbers that sum to target"
Detecting cycles in a linked list (fast/slow pointer variant)

Types of Two Pointers

Type 1: Opposite Direction (Converging)

[1, 2, 3, 4, 5, 6]
 ↑                ↑
left             right

Both pointers start at opposite ends and move inward.

Type 2: Same Direction (Fast & Slow)

[1, 2, 3, 4, 5, 6]
 ↑  ↑
slow fast

One pointer runs ahead; the slow pointer marks where valid elements go.

Java Template

// ---- Type 1: Converging (sorted array) ----
public boolean hasPairWithSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return true;
        else if (sum < target) left++;
        else right--;
    }
    return false;
}

// ---- Type 2: Fast/Slow (remove duplicates in-place) ----
public int removeDuplicates(int[] nums) {
    int slow = 0;
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1; // new length
}

// ---- Type 3: Expanding Around Center (Palindromes) ----
private int expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1; // length of the palindrome
}

Worked Example 1: 3Sum

Problem: Find all unique triplets in an unsorted array that sum to zero.

Approach:

Sort the array → enables two-pointer on the inner pair
For each element nums[i], use two pointers for the remaining subarray
Skip duplicates to avoid repeated triplets

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();

    for (int i = 0; i < nums.length - 2; i++) {
        // Skip duplicate values for the first element
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1, right = nums.length - 1;

        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];

            if (sum == 0) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                // Skip duplicates for left and right
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

Trace for [-1, 0, 1, 2, -1, -4]:

After sort: [-4, -1, -1, 0, 1, 2]

i=0 (−4): left=1, right=5 → sum=−4+(−1)+2=−3 < 0 → left++
           left=2, right=5 → sum=−4+(−1)+2=−3 < 0 → left++
           left=3, right=5 → sum=−4+0+2=−2 < 0 → left++
           left=4, right=5 → sum=−4+1+2=−1 < 0 → left++
           left=5 ≥ right → stop

i=1 (−1): left=2, right=5 → sum=−1+(−1)+2=0 ✓ → add [−1,−1,2]
           skip dup for left, right → left=3, right=4
           sum=−1+0+1=0 ✓ → add [−1,0,1]

i=2 (−1): skip (dup of i=1)
...
Result: [[-1,-1,2], [-1,0,1]]

Time: O(n²) | Space: O(1) (ignoring output)

Worked Example 2: Longest Palindromic Substring (Expand Around Center)

Problem: Find the longest contiguous palindromic substring in s.

Approach:

Every palindrome mirrors around its center. A string of length $n$ has $2n - 1$ centers (single characters for odd lengths, gaps between characters for even lengths).
For each center, expand outward as long as characters match.

public String longestPalindrome(String s) {
    if (s == null || s.isEmpty()) return "";
    int start = 0, maxLen = 1;

    for (int i = 0; i < s.length(); i++) {
        int len1 = expand(s, i, i);     // odd length palindrome (center: i)
        int len2 = expand(s, i, i + 1); // even length palindrome (center: i, i+1)
        int len = Math.max(len1, len2);

        if (len > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2;
        }
    }
    return s.substring(start, start + maxLen);
}

private int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        l--;
        r++;
    }
    return r - l - 1;
}

Time: O(n²) | Space: O(1)

Common Mistakes

Mistake	Fix
Not sorting first	Sort when using converging two pointers
Off-by-one: `left < right` vs `left <= right`	Use `<` for pairs, `<=` only when single element is valid
Missing duplicate skip	After finding a result, advance past all duplicates
Forgetting inner loop advances	Both left++ AND right-- after a match

LeetCode Problems

Easy

#	Problem	Type
125	Valid Palindrome	Converging
167	Two Sum II - Input Array is Sorted	Converging
283	Move Zeroes	Fast/Slow
344	Reverse String	Converging
977	Squares of a Sorted Array	Converging

Medium

#	Problem	Type
11	Container With Most Water	Converging
15	3Sum	Sort + converging
16	3Sum Closest	Sort + converging
18	4Sum	Sort + two loops + converging
75	Sort Colors	3-way partition (Dutch flag)
80	Remove Duplicates II	Fast/Slow
142	Linked List Cycle II	Fast/Slow on list
986	Interval List Intersections	Two list pointers

Hard

#	Problem	Type
42	Trapping Rain Water	Converging with max tracking
76	Minimum Window Substring	Sliding window variant