The Two Pointer Technique

1. Introduction: Two Sets of Eyes

Imagine you have a long list of students sorted by height, and you need to find two students whose combined height is exactly 12 feet. You could pick the first student, then walk down the entire line asking everyone else. Then pick the second student, and walk down the line again. That's exhausting ($O(N^2)$).

Alternatively, you could place a teacher at the shortest end (start) and another at the tallest end (finish). If the combined height of the two students they are pointing at is too high, the teacher at the tall end moves one step down. If it's too low, the teacher at the short end moves one step up. They instantly narrow down the search and meet in the middle in just a single pass ($O(N)$)!

This is the Two Pointer technique. It involves using two integer variables (pointers) to traverse a linear data structure simultaneously. It is one of the most elegant, heavily-tested patterns in all coding interviews.

2. Core Concept: The Two Main Variants

Unlike Sliding Window (where pointers represent the bounds of a contiguous block), standard Two Pointers usually point to two independent elements that we want to compare, swap, or mathematically combine.

Variant 1: Opposite Ends (Collision Pointers)

• Setup: left = 0, right = arr.length - 1
• Movement: Pointers move towards each other until they meet (while (left < right)).
• Use cases: Reversing an array, finding a pair sum in a sorted array, Palindrome checking.

Variant 2: Same Direction (Fast/Slow Pointers)

• Setup: slow = 0, fast = 0 (or fast = 1)
• Movement: Both pointers start at the beginning. The fast pointer scouts ahead to read data. The slow pointer stays behind to write or track data.
• Use cases: Removing duplicates in-place, moving zeros to the end, Cycle detection (in Linked Lists).

3. Beginner Code Example: Palindrome Check

A palindrome is a word that reads the same forwards and backwards. This is the absolute purest example of the "Opposite Ends" pointer pattern.

Problem Statement: Given a string, determine if it is a palindrome.

public class PalindromeCheck {
    public static boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) return true;
        
        int left = 0;
        int right = s.length() - 1;
        
        // Pointers move towards the center
        while (left < right) {
            // If characters don't match, it's not a palindrome!
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            // Move pointers inward
            left++;
            right--;
        }
        
        return true;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. We look at each character at most once, stopping early if a mismatch is found.
• Space Complexity: $O(1)$. We only created two integer variables.

4. Intermediate Code Example: Two Sum on a Sorted Array

Problem Statement: (LeetCode 167) Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Return the indices of the two numbers.

Note: Since it's sorted, we do not need to use an $O(N)$ space HashMap. We can achieve $O(1)$ space using Two Pointers!

public class TwoSumSorted {
    public static int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        
        while (left < right) {
            int currentSum = numbers[left] + numbers[right];
            
            if (currentSum == target) {
                // Return 1-indexed array as per problem description
                return new int[]{left + 1, right + 1};
            } else if (currentSum < target) {
                // Sum is too small. We need a bigger number.
                // Since the array is sorted, moving 'left' to the right increases the sum.
                left++;
            } else {
                // Sum is too large. We need a smaller number.
                // Moving 'right' to the left decreases the sum.
                right--;
            }
        }
        
        return new int[]{-1, -1}; // Not found
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. The left pointer only goes up, right only goes down. They cross exactly once.
• Space Complexity: $O(1)$. No HashMaps required because the array is sorted!

5. Advanced Code Example: Trapping Rain Water

Problem Statement: (LeetCode 42 - Hard) Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

The Insight: The water trapped above any specific bar i depends strictly on the tallest bar to its left and the tallest bar to its right. Specifically: water[i] = min(max_left, max_right) - height[i]. We can use Two Pointers moving from opposite ends to solve this in a single pass without extra memory!

public class TrappingRainWater {
    public static int trap(int[] height) {
        if (height == null || height.length == 0) return 0;
        
        int left = 0;
        int right = height.length - 1;
        
        int leftMax = 0;
        int rightMax = 0;
        int totalWater = 0;
        
        while (left < right) {
            // We always process the side with the SMALLER boundary.
            // Why? Because water is bottlenecked by the smaller height!
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left]; // Cannot hold water, update boundary
                } else {
                    totalWater += leftMax - height[left]; // Can hold water!
                }
                left++; // Move left pointer
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right]; // Cannot hold water, update boundary
                } else {
                    totalWater += rightMax - height[right]; // Can hold water!
                }
                right--; // Move right pointer
            }
        }
        
        return totalWater;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. We traverse the array exactly once.
• Space Complexity: $O(1)$. We just maintain left, right, leftMax, rightMax, and totalWater.

6. Common Mistakes Beginners Make

1. Using while (left <= right) instead of while (left < right)

   • The Mistake: Allowing pointers to cross or point to the exact same element.
   • Why it's wrong: In problems like "Two Sum", you cannot use the same element twice to form a pair. If left == right, you are adding arr[left] + arr[left]. Always use < for pair finding.

2. Using Two Pointers on an Unsorted Array for Pair Sums

   • The Mistake: Trying to use the < target / > target logic on an unsorted array.
   • Why it's wrong: Moving pointers on an unsorted array is meaningless. Moving left++ doesn't guarantee a larger number. You MUST sort the array first (which costs $O(N \log N)$), or use a HashMap.

3. Fast/Slow Pointers Array Bounds

   • The Mistake: In a fast/slow setup, writing arr[fast+1] without checking if fast is at the end of the array.
   • The Fix: Always bound the scouting pointer: while(fast < arr.length - 1).

7. Interview Q&A

Q1: If an array is unsorted, should I sort it first to use Two Pointers, or just use a HashMap? Answer: It depends on the problem constraints! If you need the exact original indices (like LeetCode 1), you cannot sort the array because sorting scrambles indices. You must use a HashMap. If you only need to return the values, sorting takes $O(N \log N)$ time and $O(1)$ space, while a HashMap takes $O(N)$ time and $O(N)$ space. Mention this trade-off to your interviewer!

Q2: (LeetCode 15) 3Sum: How do you find 3 numbers that sum to 0? Answer: Sort the array. Loop through the array with pointer i. For the remaining array to the right of i, treat it exactly like "Two Sum on a Sorted Array" using left and right pointers searching for a target of -arr[i]. This solves 3Sum in $O(N^2)$ time instead of $O(N^3)$.

Q3: (LeetCode 11) Container With Most Water: How do you decide which pointer to move? Answer: The area of the container is width * min(height[left], height[right]). To maximize area, we should always move the pointer pointing to the shorter line inward. Moving the taller line cannot possibly increase the area because the area is bottlenecked by the shorter line.

Q4: How are Two Pointers different from Sliding Window? Answer: Sliding window maintains a contiguous sub-segment of data (the space between the pointers is the "window"). Standard Two Pointers only care about the specific data at the two pointer locations, entirely ignoring the elements sitting between them.

8. Practice Problems

1. Remove Duplicates from Sorted Array (LeetCode 26)
   • Goal: Same-direction pointers. Use fast to scan, slow to write unique values.
2. Container With Most Water (LeetCode 11)
   • Hint: Opposite-ends pointers. Always move the shorter pointer inward to try and find a taller height.
3. 3Sum (LeetCode 15)
   • Hint: Sort the array. Iterate i, and use two pointers to find pairs that sum to -nums[i]. Be sure to skip duplicate values to avoid duplicate triplets!

9. Summary

• Collision Pointers: Start at opposite ends and move towards the middle. Used for sorted pair finding and reversal logic.
• Fast/Slow Pointers: Start at the same point and move in the same direction at different speeds. Used for filtering, compacting arrays, and cycle detection.
• Prerequisite: Collision pointer logic based on magnitudes (e.g., sum is too small) mandates that the underlying data is sorted.
• Space Efficiency: The Two Pointer technique is the gold standard for reducing $O(N)$ auxiliary space (like HashMaps or new arrays) down to $O(1)$ in-place operations.