Two Pointer Technique

Definition

The Two Pointer technique uses two distinct indices (pointers) to traverse an array (usually sorted) or string. Typically, one pointer starts at the beginning (left) and the other at the end (right), and they move toward each other based on specific conditions.

How it Works

1. Initialize: Set left = 0 and right = n-1.
2. Loop: While left < right:

• Check a condition (e.g., is the sum too big?).
• Move the left pointer forward or the right pointer backward to adjust.

Real-World Analogy

Folding a Sheet: If you want to find the middle of a bedsheet or fold it, you grab both corners (left and right) and bring them together until they meet in the center.

Example

Problem: Find two numbers in a sorted array that add up to a target (Target = 10).

Array: [2, 4, 6, 8, 10]

• L(2) + R(10) = 12. Too big! We need a smaller sum, so move R down.
• L(2) + R(8) = 10. Match!

Code Example (Python)

def two_sum_sorted(arr, target):
    left = 0
    right = len(arr) - 1
   
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1  # Need bigger sum
        else:
            right -= 1 # Need smaller sum
           
    return None

print(two_sum_sorted([2, 4, 6, 8, 10], 10)) # Output: [0, 3] (Values 2 and 8)

Complexity Analysis

• Time Complexity: O(N). We touch every element at most once.
• Space Complexity: O(1).

Use Cases

• Two Sum: Finding pairs in a sorted array.
• Reversing: Reversing an array or string in-place.
• Palindrome Check: Checking if a string reads the same forwards and backwards.