Two Pointers

ArrayIntermediateVery CommonAlso known as: Converging Pointers, Meet in the Middle

Two pointers start at opposite ends of a sorted array and move toward each other based on a condition, eliminating half the search space with each comparison.

Complexity Analysis

Time

O(n)

Space

O(1)

Single pass through the array with two pointers moving toward each other. No additional data structures needed, just two index variables.

Recognize This Pattern When...

Pattern Signals

Array is sorted (or can be sorted without changing the answer)
Find a pair of elements that satisfy a condition
Need O(n) time or O(1) space (can't use hash map)
Problem involves comparing elements from both ends
Looking for two indices, not two values

Preconditions

Array must be sorted (or sorting doesn't affect the answer)
Looking for a pair of elements (not single element or triplet)
Comparison-based decision: each step eliminates one possibility

When NOT to Use

Array is not sorted and sorting would change the answer (e.g., need original indices)
Looking for all pairs, not just one (may need different approach)
Problem requires finding a single element (use binary search instead)
Need to preserve element order or positions

Why It Works

Because the array is sorted, when the sum of elements at both pointers is too small, moving the left pointer right increases the sum. When the sum is too large, moving the right pointer left decreases it. This guarantees we explore all valid pairs without nested loops.

The Analogy

Imagine two people walking toward each other on a number line. If they need to meet at a specific sum, the person on the smaller number walks forward to increase the total, while the person on the larger number walks backward to decrease it. They adjust based on whether their current total is too high or too low.

The Canonical Problem

Two Sum II - Input Array Is Sorted

medium

Given a sorted array and a target sum, find two numbers that add up to the target. Return their 1-indexed positions.

Solve on LeetCode

Algorithm Template

Generic template you can adapt to most two pointers problems.

Python Template

def two_pointers(arr, target):
    left = 0
    right = len(arr) - 1

    while left < right:
        current = arr[left] + arr[right]

        if current == target:
            return [left, right]  # Found it
        elif current < target:
            left += 1   # Need larger sum
        else:
            right -= 1  # Need smaller sum

    return []  # No valid pair found

Implementations

Complete examples with explanations. Copy-paste and adapt to your problem.

def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    """
    Find two numbers in sorted array that sum to target.
    Returns 1-indexed positions (LeetCode format).

    Time: O(n), Space: O(1)
    """
    left = 0
    right = len(nums) - 1

    while left < right:
        current_sum = nums[left] + nums[right]

        if current_sum == target:
            # LeetCode uses 1-indexed
            return [left + 1, right + 1]
        elif current_sum < target:
            # Sum too small, need larger value
            left += 1
        else:
            # Sum too big, need smaller value
            right -= 1

    return []  # No solution found


# Example usage
nums = [2, 7, 11, 15]
target = 9
result = two_sum_sorted(nums, target)
print(result)  # [1, 2] (indices of 2 and 7)


# Variant: Find pair with exact difference
def find_pair_with_diff(nums: list[int], diff: int) -> list[int]:
    """Find two numbers where nums[j] - nums[i] == diff (sorted array)."""
    left = 0
    right = 1  # Same direction variant

    while right < len(nums):
        current_diff = nums[right] - nums[left]

        if left == right:
            right += 1
        elif current_diff == diff:
            return [left, right]
        elif current_diff < diff:
            right += 1  # Need larger diff
        else:
            left += 1   # Need smaller diff

    return []

Python implementation with 1-indexed return for LeetCode compatibility. Includes a same-direction variant for finding pairs with a specific difference.

/**
 * Find two numbers in sorted array that sum to target.
 * Returns 1-indexed positions (LeetCode format).
 *
 * Time: O(n), Space: O(1)
 */
function twoSumSorted(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const currentSum = nums[left] + nums[right];

    if (currentSum === target) {
      // LeetCode uses 1-indexed
      return [left + 1, right + 1];
    } else if (currentSum < target) {
      // Sum too small, need larger value
      left++;
    } else {
      // Sum too big, need smaller value
      right--;
    }
  }

  return []; // No solution found
}


// Example usage
const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSumSorted(nums, target)); // [1, 2]


// Variant: Container With Most Water
function maxArea(heights) {
  let left = 0;
  let right = heights.length - 1;
  let maxWater = 0;

  while (left < right) {
    // Area = width * min(height)
    const width = right - left;
    const height = Math.min(heights[left], heights[right]);
    maxWater = Math.max(maxWater, width * height);

    // Move the shorter line inward (greedy choice)
    if (heights[left] < heights[right]) {
      left++;
    } else {
      right--;
    }
  }

  return maxWater;
}

JavaScript implementation with the classic Two Sum II solution plus Container With Most Water variant showing greedy pointer movement.

Pattern Variations

Same Direction (Fast/Slow)

O(n) / O(1)

Both pointers start at the beginning and move in the same direction at different speeds. Used for finding pairs with a specific difference or detecting cycles.

Remove Duplicates from Sorted ArrayMove ZeroesLinked List Cycle

Three Pointers (3Sum)

O(n²) / O(1)

Fix one element, then use two pointers on the remaining array. Extends to 4Sum, kSum by nesting.

3Sum3Sum Closest4Sum

Container/Area Problems

O(n) / O(1)

Maximize area between two lines. Move the pointer at the shorter height inward (greedy).

Container With Most WaterTrapping Rain Water

Practice Problems

Problem	Difficulty	Type	Notes
Two Sum II - Input Array Is Sorted	medium	canonical	The standard Two Pointers problem for sorted arrays
Two Sum	easy	prerequisite	Hash map solution for unsorted arrays - understand this first
Valid Palindrome	easy	variant	Compare characters from both ends moving inward
Container With Most Water	medium	variant	Greedy two pointers - move shorter line inward
3Sum	medium	follow-up	Fix one element, two pointers on rest. Handle duplicates.
3Sum Closest	medium	follow-up	Track closest sum instead of exact match
Trapping Rain Water	hard	follow-up	Advanced two pointers with left/right max tracking
Sort Colors	medium	variant	Dutch National Flag - three pointers variant

Interview Tips

Always ask: "Is the array sorted?" - this determines if Two Pointers applies
Start by explaining WHY the algorithm works (sorted property), not just the steps
Mention the O(1) space advantage over hash map solutions
Handle edge cases explicitly: empty array, single element, no valid pair
For 3Sum/4Sum, explain the reduction to 2Sum clearly

Common Follow-up Questions

What if the array has duplicates?

Common

For finding ANY pair: duplicates don't matter. For finding ALL unique pairs (like 3Sum): skip duplicates by checking if nums[i] == nums[i-1] and continuing.

What if the array is not sorted?

Common

Option 1: Sort first in O(n log n), then use Two Pointers. Option 2: Use a hash map for O(n) time but O(n) space. Choose based on whether you need to preserve indices.

Can you find ALL pairs that sum to target?

Common

Yes, but don't return immediately when found. Record the pair, then move BOTH pointers (left++, right--) and continue. Skip duplicates to avoid duplicate pairs.

What if we need the count of pairs instead of the pairs themselves?

When you find a match, count duplicates on both sides. If nums[left] == nums[right], use combination formula C(count, 2). Otherwise multiply left duplicates by right duplicates.

How would you extend this to 3Sum?

Common

Sort the array. For each element i, use Two Pointers on the remaining array [i+1...n-1] with target = -nums[i]. Skip duplicate values of i to avoid duplicate triplets. Time: O(n²).

Common Mistakes

Using Two Pointers on an unsorted array

Example

# WRONG: Array not sorted
nums = [3, 1, 4, 1, 5]
left, right = 0, len(nums) - 1
# Two pointers won't work - no ordering guarantee

Fix: Always check if the array is sorted. If not, either sort it first (if indices don't matter) or use a hash map instead.

Off-by-one error in loop condition

Example

# WRONG: Using <= instead of <
while left <= right:  # Will compare element with itself
    if nums[left] + nums[right] == target:
        return [left, right]  # Could return [i, i]

Fix: Use while left < right to ensure you're comparing two DIFFERENT elements. For palindrome checking where you might need to compare the same middle character, <= can be correct.

Not handling the "no solution" case

Example

# WRONG: Assuming solution always exists
def two_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        # ... logic ...
    return [left, right]  # Returns invalid indices if no solution

Fix: Always return an explicit "not found" value (empty array, None, or -1 indices) after the loop. Never assume a solution exists.

Moving the wrong pointer

Example

# WRONG: Moving left when sum is too big
if current_sum > target:
    left += 1  # This increases the sum more!

Fix: Remember: left pointer holds smaller values (in sorted array), right holds larger. To decrease sum, move right pointer left. To increase sum, move left pointer right.

Frequently Asked Questions

When should I use Two Pointers vs Hash Map for Two Sum?

Use Two Pointers when: (1) array is already sorted, (2) you need O(1) space, (3) you need indices in the sorted array. Use Hash Map when: (1) array is unsorted and you need original indices, (2) O(n) space is acceptable, (3) you want simpler code. Two Pointers is O(n) time + O(1) space; Hash Map is O(n) time + O(n) space.

Why does Two Pointers work on sorted arrays?

Sorted order creates a monotonic relationship: moving left pointer right always increases the element value (and sum), while moving right pointer left always decreases it. This lets us make greedy decisions - each comparison eliminates one possibility, guaranteeing we find the answer in O(n) time without checking all O(n²) pairs.

How do I know which pointer to move?

Compare your current result to the target. If current < target, you need a larger value, so move the left pointer right (toward larger elements). If current > target, you need a smaller value, so move the right pointer left (toward smaller elements). If equal, you found it.

Can Two Pointers be used for non-sum problems?

Yes! Two Pointers works for any problem where: (1) you're comparing/combining elements from different positions, (2) sorted order lets you make greedy decisions. Examples: Valid Palindrome (compare chars from ends), Container With Most Water (maximize area), Merge Sorted Arrays (merge from ends).

What's the difference between "opposite ends" and "same direction" Two Pointers?

Opposite ends (converging): left starts at 0, right starts at end, they move toward each other. Used for sum problems, palindromes. Same direction (fast/slow): both start at beginning, move in same direction at different speeds. Used for cycle detection, removing duplicates, finding middle of linked list.

How do I handle duplicates in 3Sum?

After sorting, skip duplicate values at each level: (1) For the outer loop i, skip if nums[i] == nums[i-1]. (2) After finding a valid triplet, skip duplicates for both left and right pointers before continuing. This ensures each unique triplet is counted exactly once.

Related Patterns

Sliding Window (Fixed Size)Sliding Window (Variable Size)

Related Design Patterns

Strategy Pattern

Practice Two Pointers

Learn by implementing. Our capstone exercises walk you through building this algorithm step by step.

Available in Python and JavaScript.

← Back to Interview Prep

Two Pointers

ArrayIntermediateVery CommonAlso known as: Converging Pointers, Meet in the Middle

Two pointers start at opposite ends of a sorted array and move toward each other based on a condition, eliminating half the search space with each comparison.

Complexity Analysis

Time

O(n)

Space

O(1)

Single pass through the array with two pointers moving toward each other. No additional data structures needed, just two index variables.

Recognize This Pattern When...

Pattern Signals

Array is sorted (or can be sorted without changing the answer)
Find a pair of elements that satisfy a condition
Need O(n) time or O(1) space (can't use hash map)
Problem involves comparing elements from both ends
Looking for two indices, not two values

Preconditions

Array must be sorted (or sorting doesn't affect the answer)
Looking for a pair of elements (not single element or triplet)
Comparison-based decision: each step eliminates one possibility

When NOT to Use

Array is not sorted and sorting would change the answer (e.g., need original indices)
Looking for all pairs, not just one (may need different approach)
Problem requires finding a single element (use binary search instead)
Need to preserve element order or positions

Why It Works

The Analogy

The Canonical Problem

Two Sum II - Input Array Is Sorted

medium

Given a sorted array and a target sum, find two numbers that add up to the target. Return their 1-indexed positions.

Solve on LeetCode

Algorithm Template

Generic template you can adapt to most two pointers problems.

Python Template

def two_pointers(arr, target):
    left = 0
    right = len(arr) - 1

    while left < right:
        current = arr[left] + arr[right]

        if current == target:
            return [left, right]  # Found it
        elif current < target:
            left += 1   # Need larger sum
        else:
            right -= 1  # Need smaller sum

    return []  # No valid pair found

Implementations

Complete examples with explanations. Copy-paste and adapt to your problem.

def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    """
    Find two numbers in sorted array that sum to target.
    Returns 1-indexed positions (LeetCode format).

    Time: O(n), Space: O(1)
    """
    left = 0
    right = len(nums) - 1

    while left < right:
        current_sum = nums[left] + nums[right]

        if current_sum == target:
            # LeetCode uses 1-indexed
            return [left + 1, right + 1]
        elif current_sum < target:
            # Sum too small, need larger value
            left += 1
        else:
            # Sum too big, need smaller value
            right -= 1

    return []  # No solution found


# Example usage
nums = [2, 7, 11, 15]
target = 9
result = two_sum_sorted(nums, target)
print(result)  # [1, 2] (indices of 2 and 7)


# Variant: Find pair with exact difference
def find_pair_with_diff(nums: list[int], diff: int) -> list[int]:
    """Find two numbers where nums[j] - nums[i] == diff (sorted array)."""
    left = 0
    right = 1  # Same direction variant

    while right < len(nums):
        current_diff = nums[right] - nums[left]

        if left == right:
            right += 1
        elif current_diff == diff:
            return [left, right]
        elif current_diff < diff:
            right += 1  # Need larger diff
        else:
            left += 1   # Need smaller diff

    return []

Python implementation with 1-indexed return for LeetCode compatibility. Includes a same-direction variant for finding pairs with a specific difference.

/**
 * Find two numbers in sorted array that sum to target.
 * Returns 1-indexed positions (LeetCode format).
 *
 * Time: O(n), Space: O(1)
 */
function twoSumSorted(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const currentSum = nums[left] + nums[right];

    if (currentSum === target) {
      // LeetCode uses 1-indexed
      return [left + 1, right + 1];
    } else if (currentSum < target) {
      // Sum too small, need larger value
      left++;
    } else {
      // Sum too big, need smaller value
      right--;
    }
  }

  return []; // No solution found
}


// Example usage
const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSumSorted(nums, target)); // [1, 2]


// Variant: Container With Most Water
function maxArea(heights) {
  let left = 0;
  let right = heights.length - 1;
  let maxWater = 0;

  while (left < right) {
    // Area = width * min(height)
    const width = right - left;
    const height = Math.min(heights[left], heights[right]);
    maxWater = Math.max(maxWater, width * height);

    // Move the shorter line inward (greedy choice)
    if (heights[left] < heights[right]) {
      left++;
    } else {
      right--;
    }
  }

  return maxWater;
}

JavaScript implementation with the classic Two Sum II solution plus Container With Most Water variant showing greedy pointer movement.

Pattern Variations

Same Direction (Fast/Slow)

O(n) / O(1)

Both pointers start at the beginning and move in the same direction at different speeds. Used for finding pairs with a specific difference or detecting cycles.

Remove Duplicates from Sorted ArrayMove ZeroesLinked List Cycle

Three Pointers (3Sum)

O(n²) / O(1)

Fix one element, then use two pointers on the remaining array. Extends to 4Sum, kSum by nesting.

3Sum3Sum Closest4Sum

Container/Area Problems

O(n) / O(1)

Maximize area between two lines. Move the pointer at the shorter height inward (greedy).

Container With Most WaterTrapping Rain Water

Practice Problems

Problem	Difficulty	Type	Notes
Two Sum II - Input Array Is Sorted	medium	canonical	The standard Two Pointers problem for sorted arrays
Two Sum	easy	prerequisite	Hash map solution for unsorted arrays - understand this first
Valid Palindrome	easy	variant	Compare characters from both ends moving inward
Container With Most Water	medium	variant	Greedy two pointers - move shorter line inward
3Sum	medium	follow-up	Fix one element, two pointers on rest. Handle duplicates.
3Sum Closest	medium	follow-up	Track closest sum instead of exact match
Trapping Rain Water	hard	follow-up	Advanced two pointers with left/right max tracking
Sort Colors	medium	variant	Dutch National Flag - three pointers variant

Interview Tips

Always ask: "Is the array sorted?" - this determines if Two Pointers applies
Start by explaining WHY the algorithm works (sorted property), not just the steps
Mention the O(1) space advantage over hash map solutions
Handle edge cases explicitly: empty array, single element, no valid pair
For 3Sum/4Sum, explain the reduction to 2Sum clearly

Common Follow-up Questions

What if the array has duplicates?

Common

For finding ANY pair: duplicates don't matter. For finding ALL unique pairs (like 3Sum): skip duplicates by checking if nums[i] == nums[i-1] and continuing.

What if the array is not sorted?

Common

Option 1: Sort first in O(n log n), then use Two Pointers. Option 2: Use a hash map for O(n) time but O(n) space. Choose based on whether you need to preserve indices.

Can you find ALL pairs that sum to target?

Common

Yes, but don't return immediately when found. Record the pair, then move BOTH pointers (left++, right--) and continue. Skip duplicates to avoid duplicate pairs.

What if we need the count of pairs instead of the pairs themselves?

When you find a match, count duplicates on both sides. If nums[left] == nums[right], use combination formula C(count, 2). Otherwise multiply left duplicates by right duplicates.

How would you extend this to 3Sum?

Common

Sort the array. For each element i, use Two Pointers on the remaining array [i+1...n-1] with target = -nums[i]. Skip duplicate values of i to avoid duplicate triplets. Time: O(n²).

Common Mistakes

Using Two Pointers on an unsorted array

Example

# WRONG: Array not sorted
nums = [3, 1, 4, 1, 5]
left, right = 0, len(nums) - 1
# Two pointers won't work - no ordering guarantee

Fix: Always check if the array is sorted. If not, either sort it first (if indices don't matter) or use a hash map instead.

Off-by-one error in loop condition

Example

# WRONG: Using <= instead of <
while left <= right:  # Will compare element with itself
    if nums[left] + nums[right] == target:
        return [left, right]  # Could return [i, i]

Fix: Use while left < right to ensure you're comparing two DIFFERENT elements. For palindrome checking where you might need to compare the same middle character, <= can be correct.

Not handling the "no solution" case

Example

# WRONG: Assuming solution always exists
def two_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        # ... logic ...
    return [left, right]  # Returns invalid indices if no solution

Fix: Always return an explicit "not found" value (empty array, None, or -1 indices) after the loop. Never assume a solution exists.

Moving the wrong pointer

Example

# WRONG: Moving left when sum is too big
if current_sum > target:
    left += 1  # This increases the sum more!

Fix: Remember: left pointer holds smaller values (in sorted array), right holds larger. To decrease sum, move right pointer left. To increase sum, move left pointer right.