Two Pointer Technique: Efficient Traversals for Scalable Code

After learning about the Sliding Window, we're ready to meet another powerful pattern that helps us write time-efficient, space-conscious, and scalable solutions: the Two Pointer Technique.

This is one of the most understated but effective ways to reduce time complexity in problems involving arrays, strings, or linked lists.

---

What Is the Two Pointer Technique?

The Two Pointer approach involves using two variables (or "pointers") that move across a data structure from different directions or at different speeds to solve a problem in linear time.

It’s most commonly used when:

• The data is sorted
• You want to find pairs or ranges
• You want to compare or merge two lists

---

Why Does It Matter for Complexity?

Many problems that use nested loops (O(n²)) can be reduced to O(n) with two pointers.

Instead of comparing every element with every other (slow), we strategically walk through the data using two eyes instead of one.

It’s fast. It's elegant. And it scales beautifully.

---

Example 1: Find a Pair with Given Sum in Sorted Array

❌ Brute Force (O(n²))

def has_pair_with_sum(arr, target):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] + arr[j] == target:
                return True
    return False

This checks all combinations of pairs. Works... but slow.

---

Two Pointer (O(n)) – Works Only on Sorted Arrays

def has_pair_with_sum(arr, target):
    left = 0                  # Start pointer
    right = len(arr) - 1      # End pointer

    while left < right:
        current_sum = arr[left] + arr[right]

        if current_sum == target:
            return True       # Found a matching pair

        elif current_sum < target:
            left += 1         # Move left pointer to increase sum

        else:
            right -= 1        # Move right pointer to decrease sum

    return False              # No pair found

What's Happening?

• We eliminate one possibility on every step.
• That means linear time (O(n)), not quadratic.
• The array must be sorted — or sort it first in O(n log n).

---

Exammple 2: Removing Duplicates in a Sorted Array

Given a sorted array, remove the duplicates in-place such that each element appears only once and return the new length.

You're not allowed to use extra space — so you're modifying the original array.

---

Input Example

arr = [1, 1, 2, 3, 3, 4]

Expected result:

• Modified array (in-place): [1, 2, 3, 4, _, _]
• Returned value: 4 (length of unique portion)

---

Brute Force Approach (Not In-Place)

def remove_duplicates_brute_force(arr):
    if not arr:
        return []

    result = [arr[0]]  # Start with the first element

    for i in range(1, len(arr)):
        if arr[i] != arr[i - 1]:  # Compare with previous
            result.append(arr[i])

    return result

Two Pointer (O(n))

def remove_duplicates(arr):
    if not arr:
        return 0

    write = 1  # Pointer to the position where next unique element will go

    for read in range(1, len(arr)):
        if arr[read] != arr[read - 1]:
            arr[write] = arr[read]  # Write the unique element
            write += 1              # Move the write pointer forward

    return write  # This is the new length of the deduplicated array

---

What's Going On?

We use two pointers:

Pointer	Purpose
read	Scans the array looking for unique elements
write	Marks where to overwrite the next unique value

👣 Step-by-Step Walkthrough (with arr = [1, 1, 2, 3, 3, 4]):

1. write = 1, read = 1:
   arr[1] == arr[0] → both are 1 → duplicate, so do nothing.

2. read = 2:
   arr[2] != arr[1] → 2 != 1 → new unique element
   → arr[write] = arr[2] → arr[1] = 2
   → write = 2

3. read = 3:
   3 != 2 → unique → arr[2] = 3, write = 3

4. read = 4:
   3 == 3 → duplicate → do nothing

5. read = 5:
   4 != 3 → unique → arr[3] = 4, write = 4

Finally:

arr = [1, 2, 3, 4, 3, 4]  # Modified in-place
return 4                 # Only first 4 are unique

---

Why This is Efficient

• Time Complexity: O(n) – we only scan the array once.
• Space Complexity: O(1) – no extra data structures used.
• It’s a perfect example of using two pointers to solve in-place modification problems.

Real-World Use Cases

Domain	Example
Data pipelines	Merge sorted data streams efficiently
Web crawling	Detect loops in link paths
Media processing	Normalize color ranges or pixel buffers in-place
NLP	Matching patterns and substring navigation
Interviews 😅	Any question that says “sorted” or “subarray” 😉

---

When to Use Two Pointers

Scenario	Examples
Sorted array problems	Pair sum, triplets, closest sum
Linked lists	Detect cycle (Floyd’s slow/fast pointer)
Comparing sequences	Merge sorted arrays, intersection of two lists
In-place array manipulation	Reverse array, remove elements, deduplication
Backtracking with constraints	Palindrome check, window expansion, partitioning

---

Final Thought

The Two Pointer Technique teaches us that array traversal not is a one-way street. It’s a mental unlock — realizing that you’re not limited to going left to right, or from 0 to n.

It helps manage complexity by reducing nested iteration and leads to code that scales beautifully. Combined with sliding windows, this pattern is a foundational part of building efficient software.

Don’t just loop — loop wisely.

---

✅ Up Next: Prefix Sums: Speeding Up Range Calculations