Two Pointer Technique on Arrays in DSA Python

Mental Model

Use two markers moving through the array to find pairs or conditions without checking every pair.

Analogy: Imagine two friends starting at opposite ends of a hallway, walking towards each other to find a meeting point quickly.

Array: [1] -> [2] -> [3] -> [4] -> [5]
Left pointer ↑                      Right pointer ↑

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9], target sum: 12

Goal: Find two numbers in the array that add up to 12 using two pointers

Step 1: Initialize left pointer at index 0 (value 1) and right pointer at index 4 (value 9)

[1] ↑ -> [3] -> [5] -> [7] -> [9] ↑

Why: Start checking pairs from both ends to find the target sum efficiently

Step 2: Calculate sum: 1 + 9 = 10, which is less than 12, move left pointer right

[1]    [3] ↑ -> [5] -> [7] -> [9] ↑

Why: Sum too small, increase sum by moving left pointer to higher value

Step 3: Calculate sum: 3 + 9 = 12, found target sum

[1]    [3] -> [5] -> [7] -> [9] ↑

Why: Sum matches target, pair found

Result:

Final pointers at indices 1 and 4 with values 3 and 9
Output: Pair found (3, 9)

Annotated Code

DSA Python

from typing import List, Optional

class TwoPointerArray:
    def __init__(self, arr: List[int]):
        self.arr = arr

    def find_pair_with_sum(self, target: int) -> Optional[tuple]:
        left, right = 0, len(self.arr) - 1
        while left < right:
            current_sum = self.arr[left] + self.arr[right]
            if current_sum == target:
                return (self.arr[left], self.arr[right])
            elif current_sum < target:
                left += 1
            else:
                right -= 1
        return None

if __name__ == '__main__':
    arr = [1, 3, 5, 7, 9]
    target = 12
    tp = TwoPointerArray(arr)
    result = tp.find_pair_with_sum(target)
    if result:
        print(f"Pair found {result}")
    else:
        print("No pair found")

left, right = 0, len(self.arr) - 1

initialize two pointers at array ends

while left < right:

loop until pointers meet or cross

current_sum = self.arr[left] + self.arr[right]

calculate sum of values at pointers

if current_sum == target:

check if sum matches target

return (self.arr[left], self.arr[right])

return the pair if found

elif current_sum < target:

if sum too small, move left pointer right to increase sum

left += 1

advance left pointer

else:

if sum too large, move right pointer left to decrease sum

right -= 1

move right pointer left

Output

Pair found (3, 9)

Complexity Analysis

Time: O(n) because each pointer moves at most n steps through the array once

Space: O(1) because only two pointers and a few variables are used

vs Alternative: Compared to checking all pairs (O(n^2)), two pointer technique is much faster for sorted arrays

Edge Cases

empty array

returns None immediately as no pairs exist

DSA Python

while left < right:

array with one element

returns None because no pair can be formed

DSA Python

while left < right:

no pair sums to target

returns None after pointers cross

DSA Python

return None

When to Use This Pattern

When you need to find pairs or conditions involving two elements in a sorted array, use two pointers moving inward to reduce time from quadratic to linear.

Common Mistakes

Mistake: Not moving the correct pointer based on sum comparison
Fix: If sum is less than target, move left pointer right; if sum is greater, move right pointer left

Mistake: Using two pointers on unsorted array without sorting first
Fix: Ensure array is sorted before applying two pointer technique

Summary

Find pairs or conditions in sorted arrays efficiently using two pointers from both ends.

Use when searching for pairs or sums in sorted arrays to reduce time complexity.

The key is moving pointers inward based on comparison to target sum to avoid checking all pairs.