🏃‍♂️ Two Pointers: The Dance of Two Friends

Imagine you have a long rope with colorful beads on it. Now, picture two friends—Left and Right—standing at different spots on this rope. They can walk toward each other, away from each other, or even chase one another! This is exactly how the Two Pointers technique works in programming.

🎯 What is Two Pointers?

Think of it like this:

You have a line of kids, and you need to find two kids whose heights add up to exactly 10 feet.

Instead of checking every pair (which takes forever!), you put one friend at the start and another at the end. They walk toward each other, adjusting based on what they find.

Why is this magical? 🪄

• Checking every pair: Very slow (like checking 100 × 100 = 10,000 pairs!)
• Two pointers: Super fast (just 100 steps at most!)

🎪 The Five Amazing Tricks

Let’s learn five super cool tricks using our two friends, Left and Right!

1️⃣ Two Pointers Technique (The Basic Dance)

The Story 📖

Imagine a sorted line of numbered boxes:

[1, 2, 4, 6, 8, 10]

You need to find two boxes that add up to 10.

The Dance:

1. Left starts at 1, Right starts at 10
2. 1 + 10 = 11 → Too big! Right moves left
3. 1 + 8 = 9 → Too small! Left moves right
4. 2 + 8 = 10 → Perfect! 🎉

The Code 💻

def find_pair(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:
            left += 1
        else:
            right -= 1

    return []

Visual Flow 🌊

graph TD
    A[Start: Left=0, Right=End] --> B{Sum = Target?}
    B -->|Yes| C[Found! Return pair]
    B -->|Sum < Target| D[Move Left forward]
    B -->|Sum > Target| E[Move Right backward]
    D --> F{Left < Right?}
    E --> F
    F -->|Yes| B
    F -->|No| G[No pair found]

2️⃣ Three Sum Pattern (Three Friends Join!)

The Story 📖

Now imagine THREE friends need to hold hands, and their jersey numbers must add up to 0!

Given: [-4, -1, -1, 0, 1, 2]

The Trick:

• Fix one friend (say -1)
• Use two pointers for the other two!
• Find pairs that add to 0 - (-1) = 1

The Code 💻

def three_sum(nums):
    nums.sort()
    result = []

    for i in range(len(nums) - 2):
        # Skip duplicates
        if i > 0 and nums[i] == nums[i-1]:
            continue

        left = i + 1
        right = len(nums) - 1
        target = -nums[i]

        while left < right:
            curr_sum = nums[left] + nums[right]

            if curr_sum == target:
                result.append([nums[i],
                              nums[left],
                              nums[right]])
                left += 1
                right -= 1
                # Skip duplicates
                while left < right and \
                      nums[left] == nums[left-1]:
                    left += 1
            elif curr_sum < target:
                left += 1
            else:
                right -= 1

    return result

Example 🎯

Input: [-1, 0, 1, 2, -1, -4]

Output: [[-1, -1, 2], [-1, 0, 1]]

3️⃣ Container With Most Water (The Water Game!)

The Story 📖

Picture a row of walls with different heights:

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

You want to trap the MOST water between any two walls!

The Secret:

• Water height = shorter wall
• Water area = height × distance

Why Two Pointers Work:

• Start with widest container (left=0, right=end)
• Move the SHORTER wall inward (maybe find taller one!)

The Code 💻

def max_area(height):
    left = 0
    right = len(height) - 1
    max_water = 0

    while left < right:
        width = right - left
        h = min(height[left], height[right])
        area = width * h
        max_water = max(max_water, area)

        # Move shorter wall
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water

Visual Example 🌊

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

Step 1: left=0(1), right=8(7)
        Area = 8 × min(1,7) = 8
        Move left (shorter)

Step 2: left=1(8), right=8(7)
        Area = 7 × min(8,7) = 49 ✨
        Move right (shorter)

4️⃣ Valid Palindrome (The Mirror Game!)

The Story 📖

A palindrome reads the same forwards and backwards, like:

• “racecar” → ✅
• “A man, a plan, a canal: Panama” → ✅
• “hello” → ❌

The Trick:

• Left friend starts at the beginning
• Right friend starts at the end
• They walk toward each other, checking if letters match!

The Code 💻

def is_palindrome(s):
    # Clean: keep only letters/numbers
    s = ''.join(c.lower() for c in s
                if c.isalnum())

    left = 0
    right = len(s) - 1

    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1

    return True

Walk Through 🚶

String: "racecar"

Step 1: 'r' == 'r' ✓  (left=0, right=6)
Step 2: 'a' == 'a' ✓  (left=1, right=5)
Step 3: 'c' == 'c' ✓  (left=2, right=4)
Step 4: left=3, right=3 (same spot!)

Result: PALINDROME! 🎉

graph TD
    A[Start: L=0, R=n-1] --> B{char at L == char at R?}
    B -->|Yes| C[Move both inward]
    B -->|No| D[NOT a palindrome]
    C --> E{L >= R?}
    E -->|Yes| F[IS a palindrome!]
    E -->|No| B

5️⃣ Trapping Rain Water (The Puddle Problem!)

The Story 📖

After rain, water gets trapped between tall buildings:

      █
  █   ██ █
█ ██ ████ █
-----------
[0,1,0,2,1,0,1,3,2,1,2,1]

Water fills up to the shorter of the two tallest walls on either side!

Two Pointer Magic:

• Track the tallest wall seen from left
• Track the tallest wall seen from right
• Water at any position = min(maxLeft, maxRight) - height

The Code 💻

def trap(height):
    if not height:
        return 0

    left = 0
    right = len(height) - 1
    left_max = height[left]
    right_max = height[right]
    water = 0

    while left < right:
        if left_max < right_max:
            left += 1
            left_max = max(left_max, height[left])
            water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]

    return water

Step-by-Step 💧

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

L=0, R=7: left_max=0, right_max=3
  → Move left (0 < 3)

L=1, R=7: left_max=1, right_max=3
  → water += 1-1 = 0
  → Move left

L=2, R=7: left_max=1, right_max=3
  → water += 1-0 = 1 💧
  → Move left

L=3, R=7: left_max=2, right_max=3
  → water += 2-2 = 0
  → Move left

...continue until they meet!

🎓 The Big Picture

🚀 Key Takeaways

1. Two Pointers = Two Friends moving along data
2. Usually works on sorted arrays or symmetry problems
3. Reduces time from O(n²) to O(n)
4. Move pointers based on comparison logic
5. Perfect for finding pairs, checking symmetry, or optimization

🌟 Remember This!

When you see a problem about finding pairs, checking both ends, or optimizing something with two ends—think Two Pointers!

It’s like having two scouts exploring from different directions, meeting in the middle with the answer! 🎉