Mastering the Two Pointers Technique: An In-Depth Guide

Originally published on Medium.

The world of coding interviews is filled with a variety of patterns and techniques designed to solve common algorithmic problems efficiently. One such powerful and versatile technique is the Two Pointers approach. This article aims to provide an in-depth understanding of the Two Pointers technique, its applications, and how to implement it to tackle a range of problems.

Press enter or click to view image in full size

What is the Two Pointers Technique?

The Two Pointers technique involves using two pointers (or indices) to traverse and process data structures, typically arrays or linked lists. The idea is to have one pointer start from the beginning of the structure and the other from the end (or another strategic position), and move them towards each other or in specific directions based on the problem’s requirements.

When to Use the Two Pointers Technique

The Two Pointers technique is particularly useful in scenarios such as:

1. Finding Pairs or Triplets: When looking for pairs or triplets that meet certain conditions, such as summing up to a specific value.
2. Sorting Problems: When merging sorted arrays or partitions.
3. Palindrome Checking: To verify if a string reads the same backward as forward.
4. Partitioning Arrays: To segregate elements based on certain criteria.

Example Problems and Solutions

Let’s explore some common problems where the Two Pointers technique shines.

Problem 1: Two Sum II — Input Array Is Sorted

Description: Given an array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Return the indices of the two numbers (1-indexed).

Solution:

def two_sum(numbers, target):
    left, right = 0, len(numbers) - 1
    
    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return []

# Example usage
numbers = [2, 7, 11, 15]
target = 9
print(two_sum(numbers, target))  # Output: [1, 2]

Explanation:

• We initialize two pointers, left at the beginning and right at the end of the array.
• We calculate the sum of the elements at these pointers.
• If the sum equals the target, we return the indices.
• If the sum is less than the target, we move the left pointer to the right.
• If the sum is greater than the target, we move the right pointer to the left.

Problem 2: Container With Most Water

Description: Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with the x-axis forms a container, such that the container contains the most water.

Solution:

def max_area(height):
    left, right = 0, len(height) - 1
    max_area = 0
    
    while left < right:
        width = right - left
        current_area = min(height[left], height[right]) * width
        max_area = max(max_area, current_area)
        
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_area

# Example usage
height = [1,8,6,2,5,4,8,3,7]
print(max_area(height))  # Output: 49

• We initialize two pointers, left at the beginning and right at the end of the height array.
• We calculate the area formed between the lines at these pointers and update max_area if the current area is greater.
• We move the pointer pointing to the shorter line inward, aiming to find a taller line that could potentially form a larger area.

Problem 3: Valid Palindrome

Description: Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Solution:

def is_palindrome(s):
    left, right = 0, len(s) - 1
    
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    
    return True

# Example usage
s = "A man, a plan, a canal: Panama"
print(is_palindrome(s))  # Output: True

Explanation:

• We initialize two pointers, left at the beginning and right at the end of the string.
• We skip non-alphanumeric characters and compare the remaining characters.
• If characters at left and right are not the same (ignoring cases), we return False.
• We continue moving the pointers inward until they meet.

Conclusion

The Two Pointers technique is a powerful tool for solving a wide range of problems efficiently. By strategically moving two pointers, we can simplify complex tasks and achieve optimal solutions. Mastering this technique not only enhances problem-solving skills but also prepares you for various coding interviews and competitive programming challenges.