Two Pointers

You have a gift card worth exactly 16 and a price list sorted from cheapest to most expensive: 2, 4, 5, 8, 11, 15. You want two items that use the card exactly, with nothing left over.

The obvious way is to try every pair. That works, but it is O(n²): with 10,000 prices it is about 50 million checks. Because the list is sorted, there is a much better way. Put one finger on the cheapest item and one on the most expensive, and move them toward each other.

#The idea: one finger on each end

Call the left finger L and the right finger R. Add the two prices they point at.

• If the sum is exactly the target, you are done.
• If the sum is too big, move R one step left. That is the only move that makes the sum smaller.
• If the sum is too small, move L one step right. That is the only move that makes the sum bigger.

Every step either finds the answer or moves a finger inward. The fingers can only meet once, so you check at most n pairs instead of all of them.

L = 0, R = n - 1while L < R:  sum = prices[L] + prices[R]  if sum == target: return [L, R]  if sum > target: R = R - 1  else: L = L + 1return []

#Why it is safe to throw a value away

This is the part people skip, and it is the part that makes the method correct. When you move a finger, you are claiming that the value you leave behind cannot be part of any answer.

Look at step 2. The sum 2 + 15 was too big. Every other price is at least 2, because the list is sorted. So 15 plus anything left is at least 17. No partner exists for 15, and dropping it loses nothing.

Step 3 is the mirror image. The sum 2 + 11 was too small, and 11 is now the largest price still in play. So 2 plus anything left is at most 13. Nothing can rescue 2, so it goes.

#The code

// prices is sorted from low to high.
// Returns the two positions, or [] if no pair works.
function pairWithSum(prices, target) {
  let left = 0;
  let right = prices.length - 1;
  while (left < right) {
    const sum = prices[left] + prices[right];
    if (sum === target) return [left, right];
    if (sum > target) right--; // too big: drop the largest
    else left++;               // too small: drop the smallest
  }
  return [];
}
 
pairWithSum([2, 4, 5, 8, 11, 15], 16); // [2, 4]

# prices is sorted from low to high.
# Returns the two positions, or [] if no pair works.
def pair_with_sum(prices, target):
    left, right = 0, len(prices) - 1
    while left < right:
        total = prices[left] + prices[right]
        if total == target:
            return [left, right]
        if total > target:
            right -= 1  # too big: drop the largest
        else:
            left += 1   # too small: drop the smallest
    return []
 
pair_with_sum([2, 4, 5, 8, 11, 15], 16)  # [2, 4]

Note the condition left < right, not left <= right. When the two fingers meet, they point at the same item, and an item cannot pair with itself.

#Three shapes of the same idea

"Two pointers" is a family. The pair-sum version moves the pointers toward each other, but the same trick shows up in two other shapes.

Same direction. A slow pointer marks where the next item you want to keep goes. A fast pointer scans ahead. This lets you clean up an array in place without a second array. Here it removes repeated values from a sorted list and returns how many unique values are left at the front:

function removeDuplicates(nums) {
  if (nums.length === 0) return 0;
  let slow = 0; // nums[0..slow] holds the unique values so far
  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast] !== nums[slow]) {
      slow++;
      nums[slow] = nums[fast];
    }
  }
  return slow + 1;
}
// [1, 2, 2, 2, 5, 5] becomes [1, 2, 5, ...] and returns 3

def remove_duplicates(nums):
    if not nums:
        return 0
    slow = 0  # nums[0..slow] holds the unique values so far
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1
# [1, 2, 2, 2, 5, 5] becomes [1, 2, 5, ...] and returns 3

Two lists. One pointer walks each sorted list, and at every step you take the smaller value and advance that pointer. That is the merge step at the heart of merge sort.

#Common mistakes

#Check yourself

#What to practise next

Try Squared Deviations: the input is sorted, but squaring scrambles the order, and two pointers from the ends puts it back together in one pass. When a problem asks for a window of items next to each other, like "the longest stretch with no repeats", the next tool is Sliding Window, which is the same-direction shape with a purpose.