🎯 Two Pointers: The Magic of Walking Together

The Story of Two Friends Exploring a Maze

Imagine you and your best friend are standing at different ends of a long hallway. You want to find something special in the middle. Instead of one person walking the ENTIRE hallway alone, you BOTH walk toward each other! You meet in the middle much faster!

That’s the Two Pointers technique! Two helpers exploring a list from different positions, working together to solve problems FAST.

🚶‍♂️🚶‍♀️ What is Two Pointers?

Think of it like this: You have a line of toys. Instead of checking one toy at a time from the start, you put one finger at the FIRST toy and another finger at the LAST toy. Then you move your fingers based on what you find!

// Two fingers on a list
int left = 0;           // First position
int right = arr.length - 1;  // Last position

while (left < right) {
    // Move fingers toward each other
    // based on what we find!
}

Why is this magical?

✅ Valid Palindrome: The Mirror Word Game

The Story

A palindrome is like looking in a mirror! The word reads the same forwards AND backwards.

🪞 “racecar” → YES! Same both ways! 🪞 “hello” → NO! Different backwards!

How Two Pointers Help

Put one finger at the START, one at the END. If both letters match, move BOTH fingers toward the middle!

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

    while (left < right) {
        char leftChar = s.charAt(left);
        char rightChar = s.charAt(right);

        // Skip non-letters/numbers
        if (!Character.isLetterOrDigit(leftChar)) {
            left++;
            continue;
        }
        if (!Character.isLetterOrDigit(rightChar)) {
            right--;
            continue;
        }

        // Compare (ignore uppercase/lowercase)
        if (Character.toLowerCase(leftChar)
            != Character.toLowerCase(rightChar)) {
            return false;
        }

        left++;
        right--;
    }
    return true;
}

Visual Journey

graph TD
    A["🔤 r a c e c a r"] --> B["👆left=r, right=r👆"]
    B --> C["✅ Match! Move both inward"]
    C --> D["👆left=a, right=a👆"]
    D --> E["✅ Match! Keep going..."]
    E --> F["🎉 All matched = PALINDROME!"]

🎯 Three Sum Pattern: Finding the Perfect Trio

The Story

Imagine you have a bag of coins with different values (some positive, some negative). Can you pick EXACTLY 3 coins that add up to ZERO?

Example: Coins: [-1, 0, 1, 2, -1, -4]

• Pick: -1 + 0 + 1 = 0 ✅
• Pick: -1 + 2 + -1 = 0 ✅

The Magic Trick

1. Sort the coins first (put them in order)
2. Pick one coin (call it the “anchor”)
3. Use Two Pointers to find two more coins that balance it out!

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

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

        int left = i + 1;
        int right = nums.length - 1;
        int target = -nums[i];  // What we need

        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++;
                }
            } else if (sum < target) {
                left++;   // Need bigger sum
            } else {
                right--;  // Need smaller sum
            }
        }
    }
    return result;
}

Why Sort First?

graph TD
    A["Unsorted: 4, -1, 2, -1, 0"] --> B["Sorted: -1, -1, 0, 2, 4"]
    B --> C["Pick anchor: -1"]
    C --> D["Two pointers find: 0 + 1 = ❌"]
    D --> E["Adjust pointers smartly!"]
    E --> F["Find: -1 + 0 + 1 = 0 ✅"]

🏊 Container With Most Water: The Swimming Pool Problem

The Story

You have vertical walls of different heights. You want to fill water between TWO walls. Which two walls hold the MOST water?

Think of it like this: Tall walls far apart = LOTS of water! 🌊

The Rules

• Water height = shorter wall (water spills over short ones!)
• Water width = distance between walls
• Area = height × width

Two Pointer Magic

Start with walls at the VERY ENDS (maximum width). Then move the SHORTER wall inward, hoping to find a taller one!

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

    while (left < right) {
        // Calculate current water
        int h = Math.min(height[left],
                         height[right]);
        int width = right - left;
        int water = h * width;

        maxWater = Math.max(maxWater, water);

        // Move the shorter wall
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxWater;
}

Visual Example

Heights: [1, 8, 6, 2, 5, 4, 8, 3, 7]

    8       8
    |   6   |       7
    | 5 | 5 | 4     |
    | | | | | | 3   |
  1 | | | 2 | | | | |
  -------------------------
  0 1 2 3 4 5 6 7 8

Best: walls at index 1 and 8
Height = min(8,7) = 7
Width = 8-1 = 7
Water = 7 × 7 = 49 🏆

🌧️ Trapping Rain Water: Catching Every Drop!

The Story

After rain, water gets TRAPPED between tall buildings. How much water stays on the rooftops?

This is the HARDEST pattern - but you’re ready! 💪

The Secret

For each position, water trapped = min(tallest left, tallest right) - current height

Two Pointer Approach

Track the maximum height seen from both sides as you go!

public int trap(int[] height) {
    if (height.length == 0) return 0;

    int left = 0;
    int right = height.length - 1;
    int leftMax = 0;
    int rightMax = 0;
    int water = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            // Left side is limiting
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                water += leftMax - height[left];
            }
            left++;
        } else {
            // Right side is limiting
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                water += rightMax - height[right];
            }
            right--;
        }
    }

    return water;
}

Visual Example

Heights: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

        3
    2   | 2   2
  1 | 1 | | | | 1 1
  | | | | | | | | |
  0 1 2 3 4 5 6 7 8 9 10 11

Water trapped (shown as ~):
        3
    2 ~ | 2 ~ 2
  1 | 1 | | ~ | 1 1

Total water = 6 units! 🌊

🧠 When to Use Two Pointers?

Ask yourself these questions:

🎮 Pattern Recognition Cheat

graph TD
    A["Problem Type?"] --> B{"Sorted Array?"}
    B -->|Yes| C["Two Sum → Two Pointers"]
    B -->|No| D{"Need to sort first?"}
    D -->|Yes| E["Three Sum → Sort + Two Pointers"]
    D -->|No| F{"Compare ends?"}
    F -->|Yes| G["Palindrome/Container"]
    F -->|No| H{"Track max both sides?"}
    H -->|Yes| I["Trapping Rain Water"]

🏆 Key Takeaways

1. Two Pointers = Two friends exploring together - faster than one!

2. Start positions matter:

   • Same direction: Slow & Fast pointer
   • Opposite ends: Shrinking window

3. Movement rules:

   • Move based on comparison
   • Move the “weaker” pointer to find better options

4. Time complexity: Usually O(n) - visit each element once!

5. Space complexity: Usually O(1) - just two pointers!

🚀 You’re Now a Two Pointer Pro!

You learned:

• ✅ Valid Palindrome - Mirror check with two ends
• 🎯 Three Sum - Anchor + two pointer search
• 🏊 Container With Most Water - Move the shorter wall
• 🌧️ Trapping Rain Water - Track maximums from both sides

Remember: When you see arrays and need to avoid O(n²), think TWO POINTERS! Your code will run like a cheetah instead of crawling like a snail! 🐆💨