Two Pointers: Collision and Fast-Slow Techniques

What are Two Pointers?

The Two Pointers technique leverages the order or structural properties of an array. By using two cursors instead of a nested loop, it reduces complexity from O(n²) to O(n).

Based on the direction of movement:

• Collision Pointers (Opposite Direction): left starts at the beginning, right starts at the end, and they move toward each other.
• Fast & Slow Pointers (Same Direction): Both pointers move in the same direction, typically with the fast pointer staying ahead.

Collision Pointers

Moving from both ends toward the middle, the core logic is to move the side that definitely cannot contribute to a better solution.

Two Sum II (LeetCode 167)

In a sorted array, find two numbers such that they add up to a target:

int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) return new int[]{left + 1, right + 1};
        if (sum < target) left++;   // Sum too small, move left pointer right to increase
        else right--;               // Sum too large, move right pointer left to decrease
    }
    return new int[]{-1, -1};
}

Why does this work? Because the array is sorted. If sum < target, right is already the largest possible value; pairing it with the current left isn't enough, so no other pairing for the current left will work. Thus, we move left. Symmetric logic applies when sum > target.

{
  "type": "array-pointer",
  "title": "Two Sum II — target=9, nums=[2,3,4,6,8,11]",
  "steps": [
    {
      "note": "Initial: left=0, right=5, sum=2+11=13 > 9, move right",
      "array": [2, 3, 4, 6, 8, 11],
      "pointers": { "L": 0, "R": 5 },
      "highlight": [0, 5]
    },
    {
      "note": "sum=2+8=10 > 9, continue moving right",
      "array": [2, 3, 4, 6, 8, 11],
      "pointers": { "L": 0, "R": 4 },
      "highlight": [0, 4]
    },
    {
      "note": "sum=2+6=8 < 9, move left",
      "array": [2, 3, 4, 6, 8, 11],
      "pointers": { "L": 0, "R": 3 },
      "highlight": [0, 3]
    },
    {
      "note": "sum=3+6=9 == target, found! Returns [2,4] (1-indexed)",
      "array": [2, 3, 4, 6, 8, 11],
      "pointers": { "L": 1, "R": 3 },
      "highlight": [1, 3],
      "matched": [1, 3]
    }
  ]
}

Reverse String (LeetCode 344)

Classic collision: swap elements and shrink toward the center:

void reverseString(char[] s) {
    int left = 0, right = s.length - 1;
    while (left < right) {
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}

3Sum (LeetCode 15)

Fix one number, then use two pointers for the remaining sum:

List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;  // Skip duplicates
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                // Skip duplicates for the next results
                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 res;
}

Fast & Slow Pointers

Moving in the same direction, usually with fast exploring more quickly than slow to perform in-place modifications.

Remove Duplicates from Sorted Array (LeetCode 26)

slow tracks the last unique element's position, while fast looks for the next new value:

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];  // Write unique element
        }
    }
    return slow + 1;
}

{
  "type": "array-pointer",
  "title": "Remove Duplicates [1,1,2,3,3,4]",
  "steps": [
    {
      "note": "slow=0, fast=1, nums[1]==nums[0], skip fast",
      "array": [1, 1, 2, 3, 3, 4],
      "pointers": { "slow": 0, "fast": 1 },
      "highlight": [0, 1]
    },
    {
      "note": "fast=2, nums[2]=2 != nums[0]=1, slow++, write nums[1]=2",
      "array": [1, 2, 2, 3, 3, 4],
      "pointers": { "slow": 1, "fast": 2 },
      "highlight": [1, 2]
    },
    {
      "note": "fast=3, nums[3]=3 != nums[1]=2, slow++, write nums[2]=3",
      "array": [1, 2, 3, 3, 3, 4],
      "pointers": { "slow": 2, "fast": 3 },
      "highlight": [2, 3]
    },
    {
      "note": "fast=4, nums[4]=3 == nums[2]=3, skip fast",
      "array": [1, 2, 3, 3, 3, 4],
      "pointers": { "slow": 2, "fast": 4 },
      "highlight": [2, 4]
    },
    {
      "note": "fast=5, nums[5]=4 != nums[2]=3, slow++, write nums[3]=4. End, return slow+1=4",
      "array": [1, 2, 3, 4, 3, 4],
      "pointers": { "slow": 3, "fast": 5 },
      "highlight": [3, 5],
      "matched": [0, 1, 2, 3]
    }
  ]
}

Move Zeroes (LeetCode 283)

Move non-zero elements forward, then fill the remainder with zeros:

void moveZeroes(int[] nums) {
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            nums[slow++] = nums[fast];
        }
    }
    while (slow < nums.length) {
        nums[slow++] = 0;
    }
}

Container With Most Water (LeetCode 11)

height[left] and height[right] constrain the area. Move the shorter side: moving the shorter side is the only way to potentially increase the area; moving the longer side will always decrease the area (as the width is already shrinking).

int maxArea(int[] height) {
    int left = 0, right = height.length - 1, res = 0;
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        res = Math.max(res, area);
        if (height[left] < height[right]) left++;
        else right--;
    }
    return res;
}

When to Use Which Technique?

void moveZeroes(int[] nums) {
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            nums[slow++] = nums[fast];
        }
    }
    while (slow < nums.length) {
        nums[slow++] = 0;
    }
}

盛最多水的容器（LeetCode 11）

height[left] 和 height[right] 决定面积，每次移动更矮的那侧：移动矮侧才可能让面积增大；移动高侧面积只会减小（宽度已在缩小）。

int maxArea(int[] height) {
    int left = 0, right = height.length - 1, res = 0;
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        res = Math.max(res, area);
        if (height[left] < height[right]) left++;
        else right--;
    }
    return res;
}

选择对撞指针还是快慢指针？