Two Pointers Pattern

What is Two Pointers?

The Two Pointers pattern uses two pointers to traverse an array or string, typically moving towards each other or in the same direction. It transforms O(n²) brute force solutions into O(n) optimal ones.

Quick Recognition: If you see a sorted array + need to find pairs/triplets + want O(1) space, Two Pointers is likely the answer!

Pattern Recognition Checklist

Before using Two Pointers, ask yourself:

Use Two Pointers When

Array is sorted (or can be sorted)
Need to find pairs with a property
In-place modification required
Need to compare elements from ends
Want to avoid O(n²) nested loops

Don't Use When

Need to preserve original order
Array is unsorted and sorting changes answer
Need to find subarrays (use Sliding Window)
Need lookup by value (use HashMap)

When to Use

Sorted Arrays

Finding pairs, triplets, or elements with specific sum

Palindrome Problems

Checking or creating palindromes

Merging Arrays

Merging sorted arrays or linked lists

Removing Duplicates

In-place array modifications

Pattern Variations

1. Opposite Direction (Converging)

Pointers start at both ends and move towards the center.

def two_sum_sorted(arr, target):
    """Find two numbers in sorted array that sum to target"""
    left, right = 0, 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 larger sum
        else:
            right -= 1  # Need smaller sum
    
    return [-1, -1]  # Not found

2. Same Direction (Fast & Slow)

Both pointers move in the same direction at different speeds.

def remove_duplicates(arr):
    """Remove duplicates from sorted array in-place"""
    if not arr:
        return 0
    
    slow = 0  # Points to last unique element
    
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    
    return slow + 1  # Length of unique elements

3. Container With Most Water

def max_area(height):
    """Find two lines that form container with most water"""
    left, right = 0, len(height) - 1
    max_water = 0
    
    while left < right:
        width = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, width * h)
        
        # Move the shorter line inward
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_water

4. Valid Palindrome

def is_palindrome(s):
    """Check if string is palindrome (alphanumeric only)"""
    left, right = 0, len(s) - 1
    
    while left < right:
        # Skip non-alphanumeric characters
        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

5. 3Sum

def three_sum(nums):
    """Find all unique triplets that sum to zero"""
    nums.sort()
    result = []
    
    for i in range(len(nums) - 2):
        # Skip duplicates for first element
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        left, right = i + 1, len(nums) - 1
        
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                # Skip duplicates
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    
    return result

6. Trapping Rain Water

def trap(height):
    """Calculate trapped water between elevation bars"""
    if not height:
        return 0
    
    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water = 0
    
    while left < right:
        if left_max < right_max:
            left += 1
            left_max = max(left_max, height[left])
            water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]
    
    return water

7. Move Zeroes

def move_zeroes(nums):
    """Move all zeroes to end while maintaining order"""
    slow = 0  # Position for next non-zero element
    
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

8. Sort Colors (Dutch National Flag)

def sort_colors(nums):
    """Sort array of 0s, 1s, and 2s in-place"""
    low, mid, high = 0, 0, len(nums) - 1
    
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

Classic Problems

1. Two Sum II (Sorted Array)

Problem: Find two numbers in a sorted array that add up to target.Approach: Use converging pointers. If sum is too small, move left pointer right. If too large, move right pointer left.Time: O(n) | Space: O(1)

2. Container With Most Water

Problem: Find two lines that form a container holding the most water.Approach: Start from both ends. Move the pointer with the shorter line inward (greedy choice).Time: O(n) | Space: O(1)

3. Valid Palindrome

Problem: Check if a string is a palindrome (ignoring non-alphanumeric).Approach: Compare characters from both ends, skip non-alphanumeric.Time: O(n) | Space: O(1)

4. 3Sum

Problem: Find all unique triplets that sum to zero.Approach: Sort array, fix one element, use two pointers for remaining two.Time: O(n^2) | Space: O(1) excluding output

5. Trapping Rain Water

Problem: Calculate trapped water between elevation bars.Approach: Two pointers with max height tracking from both sides.Time: O(n) | Space: O(1)

Template Code

# Template 1: Converging Pointers
def converging_template(arr):
    left, right = 0, len(arr) - 1
    result = None
    
    while left < right:
        # Process current pair
        # Update result if needed
        
        if condition_move_left:
            left += 1
        else:
            right -= 1
    
    return result

# Template 2: Fast-Slow Pointers
def fast_slow_template(arr):
    slow = 0
    
    for fast in range(len(arr)):
        if some_condition(arr[fast]):
            arr[slow] = arr[fast]
            slow += 1
    
    return slow

Common Mistakes

Avoid These Pitfalls:

Off-by-one errors: Be careful with left < right vs left <= right
Infinite loops: Ensure pointers always move towards termination
Missing edge cases: Empty arrays, single elements, all duplicates
Modifying while iterating: Be careful when removing elements in-place

Debugging Checklist

When your Two Pointers solution fails, check:

Initialization

Are left and right starting at correct positions?

Loop Condition

Should it be left < right or left <= right?

Pointer Movement

Is at least one pointer moving in each iteration?

Edge Cases

Did you handle empty array, single element, all same elements?

Duplicates

Are you skipping duplicates correctly (for unique results)?

Complexity Quick Reference

Problem Type	Time	Space	Key Insight
Two Sum (sorted)	O(n)	O(1)	Move based on sum comparison
3Sum	O(n²)	O(1)	Fix one, two-pointer on rest
Remove Duplicates	O(n)	O(1)	Slow = write position
Container Water	O(n)	O(1)	Move shorter side inward
Trap Rain Water	O(n)	O(1)	Track max from both sides
Valid Palindrome	O(n)	O(1)	Skip non-alphanumeric

Interview Problems by Company

Easy
Medium
Hard

Problem	Company	Key Concept
Two Sum II	Amazon, Google	Basic converging
Valid Palindrome	Meta, Microsoft	Character comparison
Move Zeroes	Meta, Amazon	Fast-slow technique
Remove Duplicates	All FAANG	In-place modification
Squares of Sorted Array	Amazon	Converging with squares

Problem	Company	Key Concept
3Sum	All FAANG	Fix + two pointers
Container With Water	Amazon, Google	Greedy + converging
Sort Colors	Microsoft, Meta	Dutch flag (3 pointers)
3Sum Closest	Google, Meta	Tracking closest sum
Partition Labels	Amazon	Multiple passes

Problem	Company	Key Concept
Trapping Rain Water	Google, Amazon	Track max from both sides
4Sum	Google	Nested two pointers
Minimum Window Sort	Meta	Find unsorted subarray

Interview Tips

How to Explain Your Approach

Script for interviews:

“I notice the array is sorted, which suggests Two Pointers might work here.”
“I’ll use two pointers starting at opposite ends.”
“If the sum is too small, I move left pointer right to increase it.”
“If too large, I move right pointer left to decrease it.”
“This gives us O(n) time and O(1) space.”

When Interviewer Says...

Interviewer Says	You Should Think
”Can you do better than O(n²)?”	Two Pointers or HashMap
”Can you do it in O(1) space?”	Two Pointers (not HashMap)
“The array is sorted”	Definitely Two Pointers!
”Find a pair/triplet”	Two Pointers likely
”Modify array in-place”	Fast-slow pointers

Common Follow-ups

Be ready for these follow-ups:

“What if there are duplicates?” → Skip duplicates in loop
“What if no solution exists?” → Return appropriate default
“Can you handle negative numbers?” → Usually yes, same logic
“What if array is not sorted?” → Sort first, or use HashMap

Practice Problems

Problem	Difficulty	Link
Two Sum II	Easy	LeetCode 167
Valid Palindrome	Easy	LeetCode 125
3Sum	Medium	LeetCode 15
Container With Most Water	Medium	LeetCode 11
Trapping Rain Water	Hard	LeetCode 42

Practice Roadmap

Day 1: Basics

Solve: Two Sum II, Valid Palindrome
Focus: Understanding when to move which pointer

Day 2: Fast-Slow

Solve: Move Zeroes, Remove Duplicates
Focus: In-place modifications

Day 3: Multi-pointer

Solve: 3Sum, Sort Colors
Focus: Managing multiple pointers

Day 4: Advanced

Solve: Container With Water, Trapping Rain Water
Focus: Greedy decisions with pointers

Interview Tip: When you see a sorted array or need to find pairs/triplets, immediately consider Two Pointers before jumping to HashMap.

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

What is Two Pointers?

Pattern Recognition Checklist

Use Two Pointers When

Don't Use When

When to Use

Sorted Arrays

Palindrome Problems

Merging Arrays

Removing Duplicates

Pattern Variations

1. Opposite Direction (Converging)

2. Same Direction (Fast & Slow)

3. Container With Most Water

4. Valid Palindrome

5. 3Sum

6. Trapping Rain Water

7. Move Zeroes

8. Sort Colors (Dutch National Flag)

Classic Problems

Template Code

Common Mistakes

Debugging Checklist

Complexity Quick Reference

Interview Problems by Company

Interview Tips

Practice Problems

Practice Roadmap

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

​What is Two Pointers?

​Pattern Recognition Checklist

Use Two Pointers When

Don't Use When

​When to Use

Sorted Arrays

Palindrome Problems

Merging Arrays

Removing Duplicates

​Pattern Variations

​1. Opposite Direction (Converging)

​2. Same Direction (Fast & Slow)

​3. Container With Most Water

​4. Valid Palindrome

​5. 3Sum

​6. Trapping Rain Water

​7. Move Zeroes

​8. Sort Colors (Dutch National Flag)

​Classic Problems

​Template Code

​Common Mistakes

​Debugging Checklist

​Complexity Quick Reference

​Interview Problems by Company

​Interview Tips

​Practice Problems

​Practice Roadmap

What is Two Pointers?

Pattern Recognition Checklist

When to Use

Pattern Variations

1. Opposite Direction (Converging)

2. Same Direction (Fast & Slow)

3. Container With Most Water

4. Valid Palindrome

5. 3Sum

6. Trapping Rain Water

7. Move Zeroes

8. Sort Colors (Dutch National Flag)

Classic Problems

Template Code

Common Mistakes

Debugging Checklist

Complexity Quick Reference

Interview Problems by Company

Interview Tips

Practice Problems

Practice Roadmap