Two Pointers

Why Do We Even Need Two Pointers?

When we first learn arrays, our brain naturally jumps to nested loops.

Want to find a pair?
Use two loops.

Want to compare elements?
Two loops.

Works? Yes.
Efficient? Not really.

If an array has 10,000 elements, O(n²) means 100 million comparisons. That’s… unnecessary suffering.

This is where the Two Pointers pattern quietly saves the day.

---

What Is the Two Pointers Pattern?

Instead of scanning the array again and again, we use two indices to traverse it intelligently.

There are two main styles:

1. Opposite Direction Pointers (Left–Right)

   When to Use

   • Sorted array

   • Finding a pair

   • Palindrome / symmetry

   • Shrinking search space

Generic Java Template

    int left = 0;
    int right = arr.length - 1;

    while (left < right) {
        if (condition(arr[left], arr[right])) {
            // required action
            left++;
            right--;
        } else if (needToIncreaseSomething) {
            left++;
        } else {
            right--;
        }
    }

Why It Works

Since the array is sorted (in most cases), you can:

• Move left → increase value

• Move right → decrease value

No nested loops. Just one pass.

Time: O(n)
Space: O(1)

---

Same Direction Pointers (Slow–Fast)

When to Use

• Remove duplicates

• Move zeroes

• In-place modification

• Compact valid elements

Generic Java Template

int slow = 0;

for (int fast = 0; fast < arr.length; fast++) {
    if (condition(arr[fast])) {
        arr[slow] = arr[fast];
        slow++;
    }
}

Fast → scans the array
Slow → keeps track of correct placement

Again, single traversal.

Time: O(n)
Space: O(1)

---

How to Recognize Two Pointers Quickly

Look for keywords like:

• “Sorted array”

• “Find a pair”

• “Palindrome”

• “In-place”

• “Remove duplicates”

• “Two elements”

• “Subarray boundaries”

Whenever you feel tempted to write two loops, pause and ask:

Can I solve this by moving boundaries instead?

Most of the time, yes.

---

Practice Questions (LeetCode)

Start from basic → then move to slightly tricky ones.

1. Two Sum II - Input Array Is Sorted
   Classic opposite direction pointers.

2. Valid Palindrome
   Simple symmetry check using left–right.

3. Container With Most Water
   Boundary shrinking logic.

4. Remove Duplicates from Sorted Array
   Slow–fast pointer classic.

5. Move Zeroes
   Compact valid elements.

6. 3Sum
   Sorting + Two Pointers combo.

7. Squares of a Sorted Array
   Opposite direction trick.

8. Sort Colors
   Partitioning with pointers.

9. Minimum Size Subarray Sum
   Leads toward Sliding Window.

10. Boats to Save People
    Greedy + Two Pointers mix.

---

Final Takeaway

Two Pointers isn’t just a trick.

It trains you to:

• Use structure (like sorting)

• Reduce unnecessary comparisons

• Think in terms of boundaries

And once that thinking develops, nested loops start feeling unnecessary.