Two Pointers - Step by Step Understanding

What is Two Pointers?

Two pointers means:

• We use two positions (indices) in the array
• Usually called:
  • left
  • right

We move them based on conditions.

---

Why Do We Use Two Pointers?

Let us take a simple problem:

Find two numbers whose sum equals target.

Brute Force

for i in range(n):
    for j in range(i + 1, n):
        if arr[i] + arr[j] == target:
            print(i, j)

Time complexity: O(n²)

This is slow.

Better Idea (Two Pointers)

If the array is sorted:

arr = [1, 2, 3, 4, 5]
target = 6

We can solve in O(n).

---

Pattern 1: Pair Sum - pair_sum

def pair_sum(arr, target):
    left = 0
    right = len(arr) - 1

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

        if s == target:
            return True

        elif s < target:
            left += 1

        else:
            right -= 1

    return False

Step-by-Step Example

arr = [1, 2, 3, 4, 5]
target = 6

Steps:

• left = 0 (1), right = 4 (5) → sum = 6 → found

Important Logic

Condition	Action
Sum smaller than goal	left += 1
Sum larger than goal	right -= 1
Sum equals goal	found

Why This Works?

Because the array is sorted:

• Moving left increases the sum (generally toward larger values on the left side as you shrink from the smallest side).
• Moving right decreases the sum.

---

Pattern 2: Pair Counting - pair_counting

Sometimes we need to count how many pairs satisfy a condition.

Example: Count pairs with sum ≤ target.

def count_pairs(arr, target):
    left = 0
    right = len(arr) - 1
    count = 0

    while left < right:
        if arr[left] + arr[right] <= target:
            count += (right - left)
            left += 1
        else:
            right -= 1

    return count

Why count += (right - left)?

Because:

If arr[left] + arr[right] is valid,

then pairing this arr[left] with arr[left + 1] … arr[right] also produces valid sums (under the usual monotone assumptions used with this counting template).

(Always validate the invariant for your exact statement - constraints on duplicates affect correctness.)

---

Pattern 3: Choosing Pointer Movement - pair_selection_strategy

This is the most important skill.

Always ask:

• Is the current sum too small?
• Is it too large?

Then decide movement.

---

Pattern 4: Incremental Pair Update - incremental_pair_update

Sometimes the array changes, and we want to update pair-based answers without recomputing everything.

Simple example: maintain how many adjacent pairs have even sum.

arr = [1, 3, 2, 4]

def is_even_pair(a, b):
    return (a + b) % 2 == 0

count = sum(1 for i in range(len(arr) - 1) if is_even_pair(arr[i], arr[i + 1]))

If one value changes at index idx, only nearby pairs can change:

• pair (idx - 1, idx)
• pair (idx, idx + 1)

So we:

1. remove old contribution of affected pairs
2. update the value
3. add new contribution of affected pairs

This local-update idea is the core of incremental pair update.

---

Pattern 5: Order Preservation - order_preservation

Some two-pointer problems require keeping the original relative order of valid elements.

Example: move zeros to the end while preserving non-zero order.

def move_zeros_stable(nums):
    write = 0

    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1

For nums = [0, 1, 0, 3, 12], output is [1, 3, 12, 0, 0]. Notice 1, 3, 12 keep the same relative order.

---

Pattern 6: Partitioning - partitioning

Partition means:

Divide the array based on a condition.

Example: Move smaller elements left, larger right.

def partition(arr, pivot):
    left = 0

    for right in range(len(arr)):
        if arr[right] < pivot:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1

Example

arr = [5, 2, 8, 1, 3]
pivot = 4

After partition (in-place reordering typical of this sweep):

[2, 1, 3, 5, 8]

---

Pattern 7: Partition Optimization - partition_optimization

Sometimes we divide into three parts:

1. Less than pivot
2. Equal to pivot
3. Greater than pivot

This is called 3-way partitioning.

Useful when duplicates exist.

---

Time Complexity

Pattern	Time
Pair sum	O(n)
Pair counting	O(n)
Partition	O(n)

---

When to Use Two Pointers?

• Array is sorted (for meet-in-middle pairs)
• Need pair / triple combinations with structure
• Need to optimize from O(n²) → O(n)
• Partitioning problems

---

Common Mistakes

• Using two pointers on an unsorted array (without proof the moves are safe)
• Wrong pointer movement rule
• Missing conditions (left < right vs left <= right - depends on task)
• Double-counting pairs

---

Practice Questions

• Find pair with sum = target
• Count pairs ≤ target
• Move all zeros to end
• Partition array based on a pivot

---

Key Understanding

Two pointers is not just a technique.

It is a way of thinking:

• Use order
• Reduce unnecessary work
• Move intelligently

---

Final Thought

Whenever you see:

• Pair problems
• Sorted arrays
• Optimization requirement

Think:

Can I use two pointers?

Continue here:

/resources/arrays/advanced