Two Pointers Approach

Efficiency is crucial when it comes to solving algorithmic problems.

One effective technique that frequently proves helpful is the Two Pointer Approach. While it may seem simple in concept, the Two Pointer Approach can greatly improve code performance in different situations.

In this guide, we'll examine the Two Pointer Approach, covering its definition, advantages, variations, identifying when to use it, and offering clear examples and implementations for better understanding.

What is the Two Pointer Algorithm?

The Two Pointer Approach is a strategy used in algorithmic problem-solving where two pointers (indexes or iterators) are used to traverse elements of a sorted sequence simultaneously.

These pointers typically start from different positions and move towards each other or in opposite directions based on specific conditions until a desired result is achieved.

This technique is especially useful for solving problems involving arrays, linked lists, or strings, where a solution requires examining elements or substrings with specific properties or relationships between them.

By efficiently managing the movement of two pointers, this technique can often lead to optimized solutions with better time or space complexity compared to brute-force approaches.

Benefits of the Two Pointer Approach

Optimized Time Complexity: By traversing the sequence simultaneously with two pointers, it often reduces time complexity to linear or near-linear, enhancing algorithmic efficiency.
Reduced Space Complexity: Unlike some other algorithms that require additional data structures, the Two Pointer Approach typically operates in constant space, making it memory-efficient.
Simplicity and Elegance: The algorithm's straightforward implementation makes it easy to understand and apply, even in complex problem.

Types of Two Pointer Approach

Two Pointers Moving Towards Each Other:

In this type, two pointers start from opposite ends of the sequence and move towards each other until they meet, often used for searching or finding pairs.
Two Pointers Moving in the Same Direction:

Here, both pointers move in the same direction through the sequence, typically used for sliding window problems or partitioning arrays.
Two Pointers with Different Speeds:

Also know as slow and fast pointer.

This type involves one pointer moving faster than the other, often useful in scenarios requiring traversal through sorted arrays or cyclic linked lists.

Image Source: GitHub

Fast and Slow patten is useful in cases where you can’t move in a backwards direction such as in a singly linked.

When to Use the Two Pointer Technique?

Here are some scenarios where the two-pointer technique can be useful:

These are just a few examples of when the two-pointer technique can be useful. In general, it's handy whenever you need to efficiently traverse or compare elements in an array or list, especially when the array or list is sorted or there are constraints on time or space complexity.

Finding pairs in a sorted array: If you have a sorted array and you need to find a pair of elements that sum up to a certain value or fulfill certain constraints, you can use the two-pointer technique to traverse the array from both ends towards the middle, adjusting the pointers based on the comparison of the sum of the elements with the target value.

Finding a subarray with a given sum: Given an array of integers and a target sum, you can use two pointers to keep track of the start and end of a subarray while adjusting them based on whether the current subarray sum is greater or less than the target sum.

Checking for a palindrome: For problems involving checking whether a string or array is a palindrome, you can use two pointers starting from the beginning and end of the string or array and move towards the center, comparing characters or elements at each step.

Merging two sorted arrays or lists: When merging two sorted arrays or lists into a single sorted array or list, you can use two pointers to iterate through the elements of both arrays or lists and merge them in sorted order.

Detecting cycles in linked lists: For problems involving detecting cycles in linked lists, you can use two pointers moving at different speeds—one pointer advancing by one node at a time, and the other advancing by two nodes at a time. If there is a cycle, the two pointers will eventually meet.

Finding the intersection of two sorted arrays or lists: When given two sorted arrays or lists, you can use two pointers to iterate through both arrays or lists simultaneously, comparing elements at each step to find the common elements (intersection).

Examples and Implementation of Two Pointer Approach

1. Two Pointers Moving Towards Each Other:

Two Sum Problem

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

   
def two_sum(nums, target):
    # Create a list of tuples where each tuple contains the index and value of each element in the input list
    # Sort the list of tuples based on the values of the elements
    nums_sorted = sorted(enumerate(nums), key=lambda x: x[1])
    
    # Initialize two pointers, left and right, to the start and end of the sorted list respectively
    left, right = 0, len(nums) - 1
    
    # Loop until the left pointer is less than the right pointer
    while left < right:
        # Calculate the sum of the elements pointed by the left and right pointers
        curr_sum = nums_sorted[left][1] + nums_sorted[right][1]
        
        # If the current sum equals the target, return the indices of the two elements
        if curr_sum == target:
            return [nums_sorted[left][0], nums_sorted[right][0]]
        # If the current sum is less than the target, move the left pointer to the right
        elif curr_sum < target:
            left += 1
        # If the current sum is greater than the target, move the right pointer to the left
        else:
            right -= 1
    
    # If no pair of elements sum up to the target, return an empty list
    return []

2. Two Pointers Moving in the Same Direction:

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

   
def trap(height):
    # Initialize variables to keep track of the maximum heights on the left and right sides, and the accumulated water
    left_max = right_max = water = 0
    
    # Initialize two pointers, left and right, to the start and end of the input list respectively
    left, right = 0, len(height) - 1
    
    # Loop until the left pointer is less than the right pointer
    while left < right:
        # If the height at the left pointer is less than the height at the right pointer
        if height[left] < height[right]:
            # Check if the current height is greater than or equal to the left maximum height seen so far
            if height[left] >= left_max:
                # Update the left maximum height
                left_max = height[left]
            else:
                # Calculate the trapped water at the current position and add it to the total water
                water += left_max - height[left]
            # Move the left pointer to the right
            left += 1
        else:  # If the height at the right pointer is less than or equal to the height at the left pointer
            # Check if the current height is greater than or equal to the right maximum height seen so far
            if height[right] >= right_max:
                # Update the right maximum height
                right_max = height[right]
            else:
                # Calculate the trapped water at the current position and add it to the total water
                water += right_max - height[right]
            # Move the right pointer to the left
            right -= 1
    
    # Return the total trapped water
    return water

3. Two Pointers with Different Speeds:

Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of the list and return its head.

    
 class ListNode:
     def __init__(self, val=0, next=None):
         self.val = val
         self.next = next
 
 def remove_nth_from_end(head, n):
     # Create a dummy node with value 0 and point its next to the head of the linked list
     dummy = ListNode(0)
     dummy.next = head
     
     # Initialize two pointers, fast and slow, to the dummy node
     fast = slow = dummy
     
     # Move the fast pointer 'n' positions ahead
     for _ in range(n):
         fast = fast.next
     
     # Move both fast and slow pointers until fast reaches the end of the list
     while fast.next:
         fast = fast.next
         slow = slow.next
     
     # At this point, slow is pointing to the node just before the node to be removed
     # Adjust the next pointer of slow to skip the nth node from the end
     slow.next = slow.next.next
     
     # Return the head of the modified linked list (excluding the nth node from the end)
     return dummy.next

Conclusion:

The Two Pointer Approach stands as a powerful tool in the arsenal of algorithmic problem-solving. Its efficiency, and simplicity make it invaluable in tackling a wide range of problems across different domains.

By understanding its nuances, identifying suitable problem scenarios, and mastering its implementation, one can significantly enhance their ability to devise elegant and efficient solutions.

Updated: Feb 11, 2024

« String Compression