Two Pointer Techniques

# CHAPTER 5

Two Pointer Techniques #

1. Chapter Introduction #

2. What is the Two Pointer Technique? #

3. Pattern 1: Opposite-End Pointers (The Convergence) #

*Example: Two Sum II (Input Array is Sorted)* *Prompt:* Find two numbers that add up to target. The array is sorted. Do not use extra space.

def twoSumSorted(nums, target):
    left = 0
    right = len(nums) - 1
    
    while left < right:
        current_sum = nums[left] + nums[right]
        
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            # Sum is too small. We need a bigger number. Move left pointer up.
            left += 1
        else:
            # Sum is too big. We need a smaller number. Move right pointer down.
            right -= 1
            
    return []
# Time: O(N), Space: O(1)

*The Logic:* Because the array is sorted, moving left increases the sum. Moving right decreases the sum. We logically hone in on the target without checking every combination.

4. Pattern 2: Fast and Slow Pointers (The Tortoise and Hare) #

*Example: Remove Duplicates from Sorted Array (In-Place)* *Prompt:* Remove duplicates so each unique element appears only once. Return the new length.

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    
    int slow = 0; // Tracks the position of the last unique element
    
    for (int fast = 1; fast < nums.length; fast++) {
        // If we find a NEW unique element
        if (nums[fast] != nums[slow]) {
            slow++; // Move slow pointer forward
            nums[slow] = nums[fast]; // Overwrite duplicate with new unique element
        }
    }
    // Length is index + 1
    return slow + 1; 
}
// Time: O(N), Space: O(1)

5. Pattern 3: Three Pointers (Sorting Colors) #

• Move mid across the array.

• If it sees a 0, swap it with low (push 0s to the front).

• If it sees a 2, swap it with high (push 2s to the back).

• If it sees a 1, leave it in the middle.

6. Real-World Scenario: Container With Most Water #

• Place left at 0, right at the end.

• The volume of water is limited by the *shorter* line.

• Calculate the area.

• *The Move:* To potentially find a larger area, you MUST move the pointer pointing to the *shorter* line inward. Moving the taller line cannot possibly increase the height of the container.

• Repeat until left >= right.

7. Mini Project: Reverse a String In-Place #

1. 1. left = 0, right = length - 1.

1. 2. While left < right:

1. 3. Swap arr[left] and arr[right].

1. 4. left++, right--.

8. Common Mistakes #

• Infinite Loops: Forgetting to explicitly increment/decrement the pointers inside the while loop, causing the program to freeze.

• Incorrect while Condition: Using while left <= right when you shouldn't. If left == right, they are pointing to the exact same element. If the problem requires *two distinct* elements, the condition MUST be while left < right.

9. Best Practices #

• In-Place Swapping: In Python, you can swap values elegantly in one line without a temporary variable: nums[left], nums[right] = nums[right], nums[left].

10. Exercises #

1. 1. If you use Fast (moves 2 steps) and Slow (moves 1 step) pointers on a Linked List, what happens when Fast reaches the end of the list? Where is Slow?

1. 2. Why does the Opposite-End pointer technique (Two Sum II) fail if the array is NOT sorted?

11. MCQs #

14. Interview Questions #

• Q: "Given an array of integers, move all 0's to the end of it while maintaining the relative order of the non-zero elements. You must do this in-place without making a copy of the array." (LeetCode 283).

15. FAQs #

• Q: If a problem says "Given a sorted array...", should I automatically think of Two Pointers?

16. Summary #

17. Next Chapter Recommendation #