Two-Pointer Overview

1. A simple problem that illustrates the motivation behind the two-pointer technique.
2. The types of problem for which you should consider using this technique.
3. A list of problems (with animated solutions!) for you to try that build upon the concepts covered here.

Problem: Two Sum

def isPairSum(nums, target):
  for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
      if nums[i] + nums[j] == target:
        return True
  return False

Eliminating Pairs

Solution

def twoSum(nums, target):
  left, right = 0, len(nums) - 1
      
  while left < right:
    current_sum = nums[left] + nums[right]
    if current_sum == target:
        return True
    if current_sum < target:
        left += 1
    else:
        right -= 1
      
  return False

Summary

• The two-pointer technique leverages the fact that the input array is sorted to eliminate the number of pairs we consider from O(n²)down to O(n).
• The two-pointers start at opposite ends of the array, and represent the pair of numbers we are currently considering.
• We repeatedly compare the sum of the current pair to the target, and move a pointer in a way that eliminates unnecessary pairs from our search.

When Do I Use This?

• Finding a pair of items that sum to a given target in an array.
• Finding a triplet of items that sum to 0 in a given array.
• Finding the maximum amount of water that can be held between two array items representing wall heights.

Practice Problems

Bonus: Additional Problems