👈👉 Part 1: Two Pointers - The Pattern That Changes Everything

📅 ⏱️ 7 min
📚 java-patterns Part 1 of 1
  1. Part 1 Part 1: Two Pointers - The Pattern That Changes Everything 📍

Two Pointers: The Pattern That Changes Everything 🚀 #

Remember when you thought nested loops were fine? Yeah, me too. Then I discovered two pointers and felt like I’d been walking everywhere when cars existed.

🎯 The Files We’re Working With #

Before we dive in, open these three files:

  • src/main/java/dev/gregross/fundamentals/arrays/TwoPointerPatternTemplate.java - Our playground
  • src/main/java/dev/gregross/fundamentals/arrays/TwoPointerPattern.java - The solution reference
  • src/test/java/dev/gregross/fundamentals/arrays/TwoPointerPatternTest.java - Our validation suite

Having them open makes this journey so much smoother!

💡 The Moment Everything Changed #

Picture this: I had a “find two numbers that sum to target” problem. My nested loop solution worked perfectly! Then someone tested it with 10,000 elements. While my laptop turned into a space heater, I discovered two pointers could solve it in ONE pass.

That’s when I realized: elegant solutions often hide in plain sight.

Pattern 1: The Palindrome Dance 💃 #

📝 The Starting Point #

Open TwoPointerPatternTemplate.java, find line 31. Here’s our canvas:

public boolean isPalindrome(String s) {
    // TODO: Initialize two pointers
    // HINT: Where should they start? Think about the ends of the string
    
    throw new UnsupportedOperationException("Implement this method");
}

🎯 The “Aha!” Moment #

The beauty hit me: two pointers can dance from opposite ends! They skip the junk, compare what matters, and meet in the middle. It’s like two friends walking toward each other in a park.

Here’s the elegant solution that emerged:

int left = 0;
int right = s.length() - 1;

while (left < right) {
    // Skip non-letters like puddles on the sidewalk
    while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
        left++;
    }
    while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
        right--;
    }
    
    // Compare characters (case doesn't matter between friends)
    if (Character.toLowerCase(s.charAt(left)) != 
        Character.toLowerCase(s.charAt(right))) {
        return false;
    }
    
    left++;
    right--;
}

return true;  // They met successfully - it's a palindrome!

🧪 Victory Lap #

Run this test to see the magic work:

mvn test -Dtest=TwoPointerPatternTest#PalindromeTests

Check out line 39 in the test file. They test everything:

  • “A man, a plan, a canal: Panama” ✓
  • “race a car” ✗
  • Empty strings (edge cases are fun!)

Golden insight: Always check left < right in inner loops too. This boundary check is your safety net!

Pattern 2: The Duplicate Eraser ✨ #

📝 The Challenge Awaits #

Line 71 in the template:

public int removeDuplicates(int[] nums) {
    // TODO: Handle edge case
    // HINT: What if the array is empty?
    
    throw new UnsupportedOperationException("Implement this method");
}

🎨 The Beautiful Mental Model #

Picture two workers in a warehouse:

  • Scout: “Found something new!”
  • Organizer: “Great! I’ll place it in the next spot.”
[1, 1, 2, 2, 3, 4, 4]
 ↑  ↑
 O  S  (Organizer waits, Scout explores)

💫 The Elegant Solution #

if (nums.length == 0) return 0;  // Empty warehouse? We're done!

int writePointer = 1;  // Position 0 is always unique (brilliant!)

for (int readPointer = 1; readPointer < nums.length; readPointer++) {
    if (nums[readPointer] != nums[readPointer - 1]) {
        nums[writePointer] = nums[readPointer];
        writePointer++;
    }
}

return writePointer;  // This is our count of unique items!

Key realization: The write pointer tells us both WHERE to write and HOW MANY unique elements we have. Two birds, one pointer! 🎯

Pattern 3: Two Sum Symphony 🎵 #

🌟 The Lightning Strike Moment #

Sorted array + find two numbers = two pointers playing in perfect harmony!

public int[] twoSum(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;
    
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        
        if (sum == target) {
            return new int[]{left + 1, right + 1};  // Found our duet!
        } else if (sum < target) {
            left++;   // Need a higher note
        } else {
            right--;  // Need a lower note
        }
    }
    
    return new int[]{-1, -1};  // No harmony found
}

🎪 Watch the Magic #

[2, 7, 11, 15], target = 9
 ↑          ↑
 L          R   Sum: 17 (too high, lower the right)
 
 ↑      ↑      Sum: 13 (still high)
 
 ↑  ↑          Sum: 9 (Perfect harmony! 🎉)

One pass. O(n). Pure elegance.

Pattern 4: The Dutch National Flag Festival 🇳🇱 #

🎨 The Creative Challenge #

Sort an array of 0s, 1s, and 2s in one pass. It’s like organizing a flag parade!

🎭 The Three-Pointer Ballet #

public void sortColors(int[] nums) {
    int low = 0;     // Red section manager
    int mid = 0;     // Current inspector
    int high = nums.length - 1;  // Blue section manager
    
    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(nums, low, mid);
            low++;
            mid++;  // We know what we placed!
        } else if (nums[mid] == 1) {
            mid++;  // White is already home
        } else {
            swap(nums, mid, high);
            high--;
            // Brilliant insight: Don't move mid! 
            // We need to inspect what we just received
        }
    }
}

The key discovery: When swapping with high, the element we get is unknown. This insight makes the algorithm work perfectly!

Pattern 5: Container With Most Water 🌊 #

💧 The Problem #

Line 177 in template. Find max water between two lines.

🧠 The Brilliant Insight #

Moving the shorter line is our only hope for improvement. Moving the taller line guarantees less water (width shrinks, height can’t compensate).

public int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int maxArea = 0;
    
    while (left < right) {
        int width = right - left;
        int minHeight = Math.min(height[left], height[right]);
        maxArea = Math.max(maxArea, width * minHeight);
        
        // The greedy choice that works beautifully!
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxArea;
}

Test with [1,8,6,2,5,4,8,3,7] → Answer: 49

Drawing this out reveals the beauty of the algorithm!

Pattern 6: The Backwards Merge Magic 🔄 #

🎯 The Challenge #

Merge array2 into array1, where array1 has extra space at the end.

💡 The Backwards Breakthrough #

Going forward overwrites data. Going backward uses empty space perfectly!

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1;      // nums1's last element
    int p2 = n - 1;      // nums2's last element
    int p = m + n - 1;   // Final position
    
    // Start from the end - brilliant!
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }
    
    // Only nums2 might have leftovers
    while (p2 >= 0) {
        nums1[p] = nums2[p2];
        p2--;
        p--;
    }
}

The insight: Working backwards transforms a tricky problem into an elegant solution!

🎮 Practice Problem Spotlight #

The template has practice problems starting at line 269. Here’s a gem:

Valid Mountain Array 🏔️ #

public boolean validMountainArray(int[] arr) {
    int n = arr.length;
    if (n < 3) return false;  // Mountains need at least 3 points!
    
    int i = 0;
    
    // Climb up
    while (i + 1 < n && arr[i] < arr[i + 1]) {
        i++;
    }
    
    // Check for valid peak
    if (i == 0 || i == n - 1) return false;
    
    // Climb down
    while (i + 1 < n && arr[i] > arr[i + 1]) {
        i++;
    }
    
    return i == n - 1;  // Did we complete the journey?
}

One pointer. One pass. Pure elegance!

🧪 Test Your Mastery #

Trust the tests - they’re your friends:

# Test everything
mvn test -Dtest=TwoPointerPatternTest

# Test specific patterns when exploring
mvn test -Dtest=TwoPointerPatternTest#PalindromeTests
mvn test -Dtest=TwoPointerPatternTest#RemoveDuplicatesTests

🎓 Key Insights from the Journey #

  1. Visualize first - Drawing pointer movement reveals the solution
  2. Boundaries matter - Edge cases often hide at array boundaries
  3. Movement rules - Each pointer should have a clear purpose
  4. Elegance emerges - The best solutions feel inevitable once you see them
  5. Tests illuminate - They show you what you haven’t considered

🚀 Your Next Adventure #

Master these patterns in the template. When you can write them from memory, you’ve internalized the magic.

Then explore Sliding Window patterns - they build beautifully on what you’ve learned here!

📎 The Big Picture #

Two pointers taught me that algorithms aren’t about memorization - they’re about seeing patterns. Once you see them, you can’t unsee them.

Now go play with the template. Break things. Fix them. Discover your own insights.

And remember: When pointers dance together, beautiful solutions emerge!

P.S. - Every time I use two pointers now, I smile. It’s like having a superpower that makes O(n²) problems bow down to O(n) elegance. 🚀