Two Pointers Technique: Solving Problems on Sorted Arrays

What is the Two Pointers Technique?

The two pointers technique involves using two indices to traverse a data structure, often in opposite directions or in a coordinated manner. This method is particularly effective for problems involving sorted arrays, as the order simplifies the logic needed for comparisons.

Why Use Two Pointers?

• Efficiency: The technique often reduces the time complexity to O(n), where nnn is the size of the array.
• Simplicity: It eliminates the need for nested loops, making the code more readable and intuitive.
• Applicability: It’s perfect for solving problems like finding pairs, triplets, or ranges in arrays.

Common Scenarios for Two Pointers

Here are some popular problems where two pointers shine:

1. Finding a Pair with a Specific Sum
2. Removing Duplicates from a Sorted Array
3. Merging Two Sorted Arrays
4. Finding Triplets with a Specific Sum
5. Partitioning an Array

We’ll explore each of these with examples.

1. Finding a Pair with a Specific Sum

Problem

Given a sorted array and a target sum, determine if there exists a pair of numbers that add up to the target.

Intuition

Since the array is sorted, you can use one pointer at the start and one at the end. Adjust the pointers based on whether the current sum is too large or too small.

Code Implementation

def find_pair_with_sum(arr, target):
    left, right = 0, len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        
        if current_sum == target:
            return (arr[left], arr[right])
        elif current_sum < target:
            left += 1  # Increase the smaller value
        else:
            right -= 1  # Decrease the larger value
    
    return None  # No pair found

Example

arr = [1, 2, 3, 4, 6, 8]
target = 10
print(find_pair_with_sum(arr, target))

Output:

(2, 8)

2. Removing Duplicates from a Sorted Array

Problem

Given a sorted array, remove duplicates in-place so that each element appears only once.

Intuition

Use two pointers: one (write_pointer) tracks the position to overwrite with a unique element, while the other (read_pointer) traverses the array.

Code Implementation

def remove_duplicates(arr):
    if not arr:
        return 0
    
    write_pointer = 1
    
    for read_pointer in range(1, len(arr)):
        if arr[read_pointer] != arr[read_pointer - 1]:
            arr[write_pointer] = arr[read_pointer]
            write_pointer += 1
    
    return write_pointer

Example

arr = [1, 1, 2, 2, 3, 4, 4]
length = remove_duplicates(arr)
print(arr[:length])  # Unique elements

Output:

[1, 2, 3, 4]

3. Merging Two Sorted Arrays

Problem

Given two sorted arrays, merge them into one sorted array.

Intuition

Use two pointers to traverse both arrays and build a merged array step by step.

Code Implementation

def merge_sorted_arrays(arr1, arr2):
    i, j = 0, 0
    merged = []
    
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            merged.append(arr1[i])
            i += 1
        else:
            merged.append(arr2[j])
            j += 1
    
    # Append remaining elements
    merged.extend(arr1[i:])
    merged.extend(arr2[j:])
    
    return merged

Example

arr1 = [1, 3, 5]
arr2 = [2, 4, 6]
print(merge_sorted_arrays(arr1, arr2))

Output:

[1, 2, 3, 4, 5, 6]

4. Finding Triplets with a Specific Sum

Problem

Given a sorted array and a target sum, find all triplets that add up to the target.

Intuition

Fix one pointer and use the two pointers technique on the remaining part of the array.

Code Implementation

def find_triplets_with_sum(arr, target):
    triplets = []
    
    for i in range(len(arr) - 2):
        left, right = i + 1, len(arr) - 1
        
        while left < right:
            current_sum = arr[i] + arr[left] + arr[right]
            
            if current_sum == target:
                triplets.append((arr[i], arr[left], arr[right]))
                left += 1
                right -= 1
            elif current_sum < target:
                left += 1
            else:
                right -= 1
    
    return triplets

Example

arr = [-1, 0, 1, 2, -1, -4]
arr.sort()  # Ensure the array is sorted
target = 0
print(find_triplets_with_sum(arr, target))

Output:

[(-1, -1, 2), (-1, 0, 1)]

5. Partitioning an Array

Problem

Partition an array such that all negative numbers appear on one side and positive numbers on the other.

Intuition

Use two pointers: one starting from the beginning and the other from the end. Swap elements as needed.

Code Implementation

def partition_array(arr):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        if arr[left] < 0:
            left += 1
        elif arr[right] >= 0:
            right -= 1
        else:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1
    
    return arr

Example

arr = [1, -2, 3, -4, -1, 5, -6]
print(partition_array(arr))

Output:

[-6, -2, -4, -1, 3, 5, 1]

Visualizing the Technique

Two Pointers in Action

Let’s demonstrate the two pointers in action for finding a pair with a specific sum.

Initial State:

Array: [1, 2, 3, 4, 6]
Target: 10
Pointers: left = 0 (1), right = 4 (6)

Iterations:

1. Step 1: 1+6=7 < 10 → Move left to 1.
2. Step 2: 2+6=8 < 10 → Move left to 2.
3. Step 3: 4+6=10 → Found the pair!

Why the Two Pointers Technique Works

1. Sorted Arrays: The order allows comparisons to guide pointer adjustments effectively.
2. Reduces Complexity: Eliminates the need for nested loops, bringing down the time complexity to O(n).
3. Flexibility: Adapts to a wide range of problems, from pair sums to partitioning.

Real-World Applications

• Finance: Matching transactions or balancing accounts.
• Data Analysis: Searching for trends or specific patterns.
• Machine Learning: Preprocessing sorted data efficiently.

Conclusion

The two pointers technique is a simple yet powerful tool for tackling problems on sorted arrays. Its ability to reduce complexity and enhance clarity makes it a must-know technique for developers and problem solvers alike. By practicing with common scenarios like pair sums, triplets, and partitioning, you’ll quickly master its use.

Have a favorite two pointers problem? Share it in the comments below, and let’s discuss!