LeetCode 167 · Two Pointers

Two Sum II, explained with a picture

Two friends, one row of lockers.

MediumTwo Pointers
▶ Watch it step by step

The problem

Given a list of numbers sorted from small to large and a target, find the two numbers that add up to the target and return their positions (LeetCode counts from 1).

Input:  [1, 3, 4, 6, 8, 11, 13, 15], target = 10
Output: [3, 4]   (positions of 4 and 6, counting from 1)

Picture it

Picture a row of lockers numbered in increasing order, with one friend at each end. They add their two locker numbers. Too big? The friend on the right steps left to a smaller locker. Too small? The friend on the left steps right to a bigger one. Because the row is sorted, each step safely rules out a locker, and they meet the answer without trying every pair.

How to recognise it

  • You need a pair that adds up to a target, and the list is already sorted.
  • Sorted order means a sum tells you which way to move: too small, use a bigger number; too big, use a smaller one.
  • The problem asks for O(1) extra space, which rules out the dictionary from Two Sum.
  • Up to 3 × 10^4 numbers, and exactly one answer is guaranteed.

Start with brute force

Try every pair (i, j) with i < j and return the first one that hits the target, counting positions from 1.

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

There are n(n − 1)/2 pairs, so time is O(n²) and space O(1). With n = 3 × 10^4 that is about 4.5 × 10^8 pair checks, too slow. A binary search for target − nums[i] from each i is O(n log n), and the Two Sum dictionary is O(n) but uses O(n) space. Neither uses the sorting fully.

From brute force to the idea

  1. Start at the extremes. Put l on the smallest number and r on the largest, and look at their sum.
  2. Too small? Move l right. If the sum is below the target, nums[l] is too small even with the largest partner left. Every other partner is smaller still, so nums[l] can never be part of the answer. Drop it.
  3. Too big? Move r left. By the same argument, nums[r] is too big even with the smallest partner, so drop it.
  4. Each step discards one number for good. The answer pair is never discarded, because a pointer only moves past a number that cannot be in it. So the pointers must reach the pair.
  5. Return positions from 1. LeetCode counts from 1, hence [l + 1, r + 1].

This is the key idea: on sorted data, the sum's direction tells you which end to drop, one number per step.

The key idea

Sorted input lets two pointers squeeze inward: sum too big → move right pointer left, too small → move left pointer right. O(n).

Python solution

def two_sum(nums, target):
    l, r = 0, len(nums) - 1
    while l < r:
        s = nums[l] + nums[r]
        if s == target:
            return [l + 1, r + 1]  # 1-based
        if s < target:
            l += 1
        else:
            r -= 1
    return []

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n²): every pair is checkedO(1): two indices
Two pointers (shown code)O(n): each step moves one pointer inwards, at most n − 1 stepsO(1): two indices and a sum

Edge cases

  • Duplicate values in the answer ([2, 2], target 4): returns [1, 2]; the two pointers are different positions.
  • Negatives ([-1, 0], target −1): returns [1, 2]; sorted order is all that matters.
  • No pair exists ([1, 2], target 10): returns []. LeetCode promises an answer, so this only matters if you reuse the function.
  • Fewer than two numbers: [5] and [] both return [] because l < r is false at once.
  • Several valid pairs: the problem rules this out. If it happened, the code would return the first pair the pointers meet.

Common mistakes

  • Writing while l <= r. When l == r, one number is added to itself: [2, 3, 7] with target 6 wrongly returns [2, 2].
  • Returning [l, r], forgetting the 1-based positions.
  • Moving both pointers after a miss, which can skip the answer.
  • Using a dictionary out of habit. It works, but it ignores the sorted order and breaks the O(1) space requirement.
Your turn: count pairs below the target

Given a sorted list and a target, count the pairs of positions i < j with nums[i] + nums[j] less than the target. For [-1, 1, 1, 2, 3] and target 2 the answer is 3. Describe your approach, then write it if you like.

Compare with our answer

Use the same two pointers, but count whole blocks at once. If nums[l] + nums[r] is below the target, then nums[l] plus any number between l + 1 and r is also below it, because those are no bigger than nums[r]. That is r - l pairs, all with l; count them and move l. Otherwise nums[r] is too big for the current l and for every l still to come, so move r.

def count_pairs_below(nums, target):
    l, r, count = 0, len(nums) - 1, 0
    while l < r:
        if nums[l] + nums[r] < target:
            count += r - l          # nums[l] pairs with l+1..r
            l += 1
        else:
            r -= 1
    return count

Time O(n), space O(1). Counting pairs one by one would be O(n²) when most pairs qualify.

A strong answer mentions: why one comparison settles r - l pairs at once, why moving r loses nothing, and the O(n) time.

Check what stuck

1. You have a sorted list of item prices and must find whether two different items cost exactly your budget, using O(1) extra memory. Which approach fits best?

2. When nums[l] + nums[r] is less than the target, why is it safe to discard nums[l] for good?

3. A learner changes the loop to while l <= r. Which call now returns a wrong answer?

Score 60% or more and the lesson is marked complete.