Two Pointers - Introduction

The Two Pointers technique uses two index variables that traverse an array (or string): either from opposite ends moving toward each other, or from the same end moving at different speeds. It eliminates the need for nested loops in many problems, reducing time complexity from O(n²) to O(n).

Share

Contents

Pattern 1: Opposite Ends

Start one pointer at the left end (left = 0) and one at the right end (right = n-1). Move them toward each other based on a condition. Requires the array to be sorted.

Template:
Java
int left = 0, right = nums.length - 1;

while (left < right) {
    int sum = nums[left] + nums[right];
    if (sum == target) {
        // found the answer
    } else if (sum < target) {
        left++;   // need a larger value
    } else {
        right--;  // need a smaller value
    }
}
Classic problem: Two Sum on sorted array:
Java
// Input: sorted nums, return indices of two numbers that add to target
public int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if      (sum == target) return new int[]{left + 1, right + 1};
        else if (sum < target)  left++;
        else                    right--;
    }
    return new int[]{};
}

Pattern 2: Same Direction (Slow & Fast)

Both pointers start at the same end. The fast pointer advances every iteration; the slow pointer advances only when a condition is met. This pattern is used for in-place operations like removing duplicates.

Template:
Java
int slow = 0;

for (int fast = 0; fast < nums.length; fast++) {
    if (/* condition — keep this element */) {
        nums[slow] = nums[fast];
        slow++;
    }
    // otherwise skip: fast advances, slow stays
}
// slow is the new length
Classic problem: Remove duplicates from sorted array:
Java
public int removeDuplicates(int[] nums) {
    int slow = 0;
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) { // new unique value
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1; // new length
}

When to Use Two Pointers
  • Finding a pair / triplet in a sorted array that satisfies a condition (Two Sum, 3Sum).
  • Container / volume problems where both ends are candidates (Container with Most Water).
  • Palindrome checks: compare characters from both ends.
  • In-place compaction: remove elements, move zeros, dedup (slow/fast pattern).
  • Problems where elements are contiguous and the array is sorted.
The opposite-ends pattern usually requires the array to be sorted. If it isn't, sort it first (adds O(n log n)) or use a HashMap approach.

Complexity
  • Time: O(n). Each pointer moves at most n times, total movement is O(2n) = O(n).
  • Space: O(1). Only two index variables, no extra space.

Two Pointer Problems

  1. Two Sum II - Input Array Is Sorted
  2. 3Sum
  3. Container With Most Water
  4. Trapping Rain Water
  5. Remove Duplicates from Sorted Array