Two Pointers

What is Two Pointers?

Two pointers is a technique where you use two variables to traverse a data structure, typically from different positions.

The Core Idea

Instead of checking every pair (O(n²)), you use two pointers that move intelligently.

Visual Example

Find pair with sum = 9 in sorted array:
arr = [1, 2, 4, 5, 6, 8, 9]

Step 1:  [1, 2, 4, 5, 6, 8, 9]
          ↑                 ↑
         left             right
         sum = 1 + 9 = 10 > 9
         → move right left

Step 2:  [1, 2, 4, 5, 6, 8, 9]
          ↑              ↑
         left          right
         sum = 1 + 8 = 9 ✓ Found!

Why It Works

In a sorted array:

• If sum is too large → move right pointer left
• If sum is too small → move left pointer right

This eliminates half the possibilities each step.

Time Complexity

O(n) - each pointer moves at most n times.

When to Use

1. Sorted array problems
2. Palindrome checking
3. Pair problems (two sum, three sum)
4. Remove duplicates
5. Merge sorted arrays

Pattern 1: Opposite Ends

Start from both ends and move inward.

// Check if string is palindrome
boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

Pattern 2: Same Direction (Fast/Slow)

Both start from same position, move at different speeds.

// Remove duplicates from sorted array
int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    
    int slow = 0;
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

Pattern 3: Partition

Partition array based on condition.

// Move all zeros to end
void moveZeroes(int[] nums) {
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            swap(nums, slow, fast);
            slow++;
        }
    }
}

Pattern 4: Two Arrays

Use pointers on two different arrays.

// Merge sorted arrays
void merge(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1, p2 = n - 1, p = m + n - 1;
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p--] = nums1[p1--];
        } else {
            nums1[p--] = nums2[p2--];
        }
    }
    while (p2 >= 0) {
        nums1[p--] = nums2[p2--];
    }
}

Pattern 5: Three Pointers

// Three Sum
List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = 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) {
                result.add(Arrays.asList(nums[i], nums[left], nums[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;
}

1. Valid Palindrome (LeetCode 125)

public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        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: O(n), Space: O(1)

2. Two Sum II (LeetCode 167)

public 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};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[] {};
}
// Time: O(n), Space: O(1)

3. Container With Most Water (LeetCode 11)

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxWater = 0;
    while (left < right) {
        int water = Math.min(height[left], height[right]) * (right - left);
        maxWater = Math.max(maxWater, water);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxWater;
}
// Time: O(n), Space: O(1)

4. Trapping Rain Water (LeetCode 42)

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;
}
// Time: O(n), Space: O(1)

5. Remove Duplicates (LeetCode 26)

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int slow = 0;
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}
// Time: O(n), Space: O(1)

Common Edge Cases

1. Empty array

if (nums.length == 0) return 0;

2. Single element

if (nums.length == 1) return specialValue;

3. All same elements

// For duplicate removal, this should return 1

4. No valid pair exists

return new int[] {};  // or -1, or false

5. Integer overflow

// Use long for sums: long sum = (long)nums[left] + nums[right];

Tips for Success

1. Identify the pattern

   • Sorted array? → Opposite ends
   • Remove duplicates? → Fast/Slow
   • Merge? → Two arrays

2. Handle duplicates explicitly

while (left < right && nums[left] == nums[left + 1]) left++;

3. Check bounds

while (left < right && left < nums.length && right >= 0)

4. Use descriptive names

int left = 0;          // not 'i'
int right = n - 1;     // not 'j'

Two Pointers vs Other Techniques