Skip to content

Two Pointers

Lesson 1 of 7 in Core Patterns · 30 min · Beginner

Two fingers on the data, moving with purpose.

Introduction

You have an $18 gift card and a shop's price list, sorted from cheapest to priciest: 1, 2, 4, 6, 8, 10, 15. Which two items cost exactly $18 together, without trying every pair?

Trying every pair works. Seven prices make 21 pairs. A hundred prices make 4,950 pairs, and the count grows with the square of the list.

But this list is sorted, and that is a clue. Take the cheapest item (1) and the priciest (15): together they cost 16, which is not enough. What does that tell you about the 1?

Lesson overview

This lesson will show you how to:

  • Explain why sorted order lets you safely discard one end.
  • Trace converging pointers through Two Sum II, one move at a time.
  • Spot sorted input or a pair that must hit a target sum.
  • Use in-place pointer moves to check palindromes with O(1) extra space.
  • Compare converging pointers with same-direction pointers.

The picture

nums1021426384105156leftrightsmallestlargestmove the one that helpsArray nums with 7 slots: 1, 2, 4, 6, 8, 10, 15. Pointers: left at index 0; right at index 6. Window from index 0 to 6. Marked: index 0 compare; index 6 compare.

Mental model

Two friends stand at opposite ends of a bookshelf where the books are sorted from cheapest to priciest. Together they must pick two books that cost exactly your budget.

If the two books cost too little, the friend on the cheap end steps toward the middle. If they cost too much, the friend on the pricey end does.

Sorted order makes every move safe: a sum that is too small can only be fixed by a bigger left number, and a sum that is too big only by a smaller right number.

Words to know

pointer
An index that remembers a position in the array. You can move it, and you can read the number under it.
converging pointers
One pointer starts at each end and they walk toward each other until they meet. This is the pair-sum shape.
same-direction pointers
Both pointers start at the front and move forward, but at different speeds or jobs. One reads ahead, the other keeps track of what is kept.
slow and fast
In the same-direction shape, slow is the writer (the end of the result so far) and fast is the reader that scouts ahead.
discard
Rule a number out for good. A pointer only moves past a number once it can't be part of any answer.
in place
Changing the array itself, using no extra array. Same-direction pointers do this by writing over numbers they no longer need.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

  • Yes: The data is sorted (or you can sort it) and you need a pair that meets a target.
  • Yes: You need to compare the two ends of something, like a palindrome check.
  • Yes: The problem says in place, or asks you to remove, partition or merge using O(1) extra space.
  • Yes: Brute force would try every pair, and sorted order tells you which side to give up on.

Not this when

  • No: The array is unsorted and you need the original indices: use a hash map.
  • No: You need a contiguous stretch whose size depends on a rule (longest, shortest): that is a sliding window.
  • No: The problem is about a cycle or the middle of a linked list: that is fast and slow pointers.

Which pattern fits?

  1. Which pattern? 1 of 5

    Given a sorted array and a target, return the positions of two numbers that add up to the target.

  2. Which pattern? 2 of 5

    Given an unsorted array, return the indices of two numbers that add up to a target.

  3. Which pattern? 3 of 5

    Find the longest run of consecutive days where the total sales stay under a budget (sales are never negative).

  4. Which pattern? 4 of 5

    Decide whether a linked list has a cycle in it, using no extra memory.

  5. Which pattern? 5 of 5

    Check whether a sentence reads the same forwards and backwards, ignoring punctuation and capital letters.

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode
  1. 1left = 0, right = n - 1
  2. while left < right:
  3. 2total = nums[left] + nums[right]
  4. 3if total == target:
  5. 6return the positions of left and right
  6. 4if total < target: left = left + 1
  7. 5otherwise: right = right - 1
  8. 6return "no pair" ([-1, -1])

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

def pair_sum(nums, target):
    left = 0
    right = len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left + 1, right + 1]
        if total < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]
Time · O(n)Space · O(1)
  • Why it never misses the answer: if the sum is too small, then left plus even the biggest number still in play falls short, so left can't be in any pair. If the sum is too big, right can't be in any pair either. Only numbers that can't be part of an answer are ever dropped.
  • Each step moves one pointer inward, so there are at most n - 1 steps: O(n). Only a few variables are kept, so the extra space is O(1).
  • The array must be sorted. If it isn't, sorting first costs O(n log n) and scrambles the original positions.
  • For the same-direction shape, slow marks the last number kept and fast reads ahead. Both only move forward, so that is O(n) time and O(1) space too.
  • LeetCode counts positions from 1, so the code returns left + 1 and right + 1, and [-1, -1] when no pair exists.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode (opens in a new tab)

Given a sorted array of integers numbers and a target, return the 1-indexed positions of the two numbers that add up to the target. Use only constant extra space.

Input

numbers = [2,7,11,15], target = 9

Output

[1,2]

Approach

  1. The array is sorted, so put left on the first number and right on the last.
  2. 2 + 15 = 17 is more than 9. Even the smallest number can't pair with 15, so drop 15 and move right back to 11.
  3. 2 + 11 = 13 is still more than 9, so drop 11 and move right back to 7.
  4. 2 + 7 = 9 is the target. The numbers sit at positions 1 and 2 counting from 1, so the answer is [1, 2].
def pair_sum(nums, target):
    left = 0
    right = len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left + 1, right + 1]
        if total < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]
Time · O(n)Space · O(1)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

  1. The numbers under left and right add up to less than the target. Why is it safe to drop the left number for good?
  2. The pointers sit on the ends of [1, 3, 5, 8] and the target is 10. 1 + 8 = 9. What happens next?
  3. Why does the converging search take O(n) time and not O(n²)?
  4. What goes wrong if you run converging pointers on an unsorted array?
  5. In remove-duplicates with slow and fast pointers, what does slow mark?

Question 1 of 5

The numbers under left and right add up to less than the target. Why is it safe to drop the left number for good?

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

  1. Solve Reverse String (opens in a new tab) (LeetCode, easy)

    Hint: Swap the two ends, then move both pointers inward until they meet.

  2. Solve Move Zeroes (opens in a new tab) (LeetCode, easy)

    Hint: It is the same-direction shape from remove-duplicates: fast reads every number and slow marks where the next non-zero belongs.

  3. Solve Squares of a Sorted Array (opens in a new tab) (LeetCode, easy)

    Hint: The biggest square is at one of the two ends, so fill the answer from the back, taking the larger end each time.

  4. Solve Boats to Save People (opens in a new tab) (LeetCode, medium)

    Hint: Sort the weights. The heaviest person either shares a boat with the lightest person or has to go alone.

  5. Solve 3Sum (opens in a new tab) (LeetCode, medium)

    Hint: Sort, fix one number, then run converging pointers on the rest. Skip repeated values so you don't report the same triple twice.

  6. Solve Sort Colors (opens in a new tab) (LeetCode, medium)

    Hint: Keep pointers for where the 0s end and where the 2s begin, and swap each number you scan into the right zone.

  7. Solve 3Sum Closest (opens in a new tab) (LeetCode, medium)

    Hint: Like 3Sum, but remember the sum closest to the target so far and move the pointers by comparing each sum with the target.

  8. Solve Trapping Rain Water (opens in a new tab) (LeetCode, hard)

    Hint: The water over a bar is limited by the shorter of the tallest bars on its two sides, so always move the pointer on the lower side.

Additional resources