Two Pointers Pattern

Overview

Use two pointers to traverse a data structure (usually array/string) from different positions or directions to solve problems efficiently in O(n) time.

When to Use

• Sorted array/list problems
• Finding pairs with specific sum/difference
• Removing duplicates in-place
• Reversing arrays/strings
• Palindrome checking
• Partitioning arrays

Two Pointer Variations: 1. Opposite Direction (converging): Start at both ends, move toward middle 2. Same Direction (fast-slow): Both start at beginning, move at different speeds 3. From Different Arrays: One pointer per array, merge/compare

Template Code

Opposite Direction (Two Sum in Sorted Array)

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, right};
        } else if (sum < target) {
            left++;   // Need larger sum
        } else {
            right--;  // Need smaller sum
        }
    }
    return new int[]{-1, -1};
}

Remove Duplicates from Sorted Array

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;

    int slow = 0;  // Position for next unique element

    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;  // Length of unique elements
}

Three Sum

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

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

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

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

            if (sum == target) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                left++;
                right--;

                // Skip duplicates
                while (left < right && nums[left] == nums[left - 1]) left++;
                while (left < right && nums[right] == nums[right + 1]) right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

Container With Most Water

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxWater = 0;

    while (left < right) {
        int width = right - left;
        int h = Math.min(height[left], height[right]);
        maxWater = Math.max(maxWater, width * h);

        // Move the shorter line inward
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxWater;
}

Trapping Rain Water

public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0;
    int water = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                water += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                water += rightMax - height[right];
            }
            right--;
        }
    }
    return water;
}

Valid Palindrome

public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;

    while (left < right) {
        // Skip non-alphanumeric
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
            left++;
        }
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
            right--;
        }

        if (Character.toLowerCase(s.charAt(left)) !=
            Character.toLowerCase(s.charAt(right))) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

Time & Space Complexity

Problem	Time	Space
Two Sum (sorted)	O(n)	O(1)
Three Sum	O(n²)	O(1)
Remove Duplicates	O(n)	O(1)
Container Water	O(n)	O(1)
Trapping Rain Water	O(n)	O(1)

Common Interview Questions

1. Two Sum II - Input array is sorted
2. Three Sum - Find all triplets that sum to zero
3. Three Sum Closest - Find triplet closest to target
4. Four Sum - Find all quadruplets that sum to target
5. Container With Most Water - Maximum water container
6. Trapping Rain Water - Calculate trapped water
7. Remove Duplicates from Sorted Array - In-place removal
8. Remove Element - Remove all instances of value
9. Move Zeroes - Move zeros to end
10. Sort Colors - Dutch National Flag (0s, 1s, 2s)
11. Valid Palindrome - Alphanumeric palindrome check
12. Valid Palindrome II - Can delete one char
13. Reverse String - In-place reversal
14. Squares of Sorted Array - Return sorted squares

Tips & Tricks

• Always consider if sorting helps (converts O(n²) to O(n))
• For sum problems, sorting + two pointers often beats hash map
• Watch for duplicate handling in results
• Same direction pointers useful for in-place modifications
• Opposite direction for "find pair" or "maximize range" problems