Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Book a call

Coding · Two pointers

Fix one, then two pointers

Lesson · 10 min read · Two pointers · Fix one, then two pointers

Sort once, fix the first value, and the rest is a pair-sum scan. The hard part of 3-sum is the duplicates and nothing else.

From pairs to triples

Once you can find a pair with a given sum in a sorted array in O(n) you'll find that triples come almost for free. You sort the array and then go through it fixing each value nums[i] in turn as the smallest of the three. What you've got left is a pair problem on nums[i+1..n−1] with a target of −nums[i], and you already know how to do that from the last module. You run n scans that are O(n) each so it's O(n²) in all, where trying every triple would have been O(n³).

Fix one

threeSum(nums)

  1. Sort nums.
  2. For each i: skip it if nums[i] equals nums[i − 1].
  3. Run lo = i + 1, hi = n − 1 towards each other looking for nums[lo] + nums[hi] = −nums[i].
  4. On a hit, record it, then move lo past every copy of nums[lo] and hi past every copy of nums[hi].

Where the duplicates come from

When I see a wrong answer to 3-sum it's nearly always got the sums right and the duplicates wrong. You'll get them from two places. If you fix the same value twice then the second scan finds every triple that the first one found. And after a hit if you only move lo one step and the next value is the same as the last one you'll get the same triple out again. Sorting is what makes both of these cheap to deal with because equal values end up sitting next to each other and you can skip them with a while loop.

You can throw every triple into a set and clean up the duplicates at the end, and it does work. I wouldn't do it in an interview though because it hides the fact that you didn't know where they came from and that's often the next thing you'll be asked.

The distinct triples summing to zero in [-1, 0, 1, 2, -1, -4].

  1. Step 1 / 12
    sorted
    -40-11-12031425
    n6

    Sorted first: [-4, -1, -1, 0, 1, 2]. Equal values are now adjacent, which is what makes the duplicate rules cheap.

  2. Step 2 / 12
    sorted
    -40i-11lo-12031425hi
    fixed-4want4

    Fix nums[0] = -4. Now find two values in the rest that sum to 4.

  3. Step 3 / 12
    sorted
    -40i-11lo-12031425hi
    sum1want4

    -1 + 2 = 1 < 4. nums[1] is too small to pair with anything left; move lo right.

  4. Step 4 / 12
    sorted
    -40i-11-12lo031425hi
    sum1want4

    -1 + 2 = 1 < 4. nums[2] is too small to pair with anything left; move lo right.

  5. Step 5 / 12
    sorted
    -40i-11-1203lo1425hi
    sum2want4

    0 + 2 = 2 < 4. nums[3] is too small to pair with anything left; move lo right.

  6. Step 6 / 12
    sorted
    -40i-11-120314lo25hi
    sum3want4

    1 + 2 = 3 < 4. nums[4] is too small to pair with anything left; move lo right.

  7. Step 7 / 12
    sorted
    -40-11i-12lo031425hi
    fixed-1want1

    Fix nums[1] = -1. Now find two values in the rest that sum to 1.

  8. Step 8 / 12
    sorted
    -40-11i-12lo031425hi
    fixed-1want1

    -1 + 2 = 1. Triplet [-1, -1, 2]. Now skip past every copy of both values.

  9. Step 9 / 12
    sorted
    -40-11i-1203lo14hi25
    fixed-1want1

    0 + 1 = 1. Triplet [-1, 0, 1]. Now skip past every copy of both values.

  10. Step 10 / 12
    sorted
    -40-11-12i031425
    fixed-1

    nums[2] = -1 repeats the previous fixed value. Every triplet starting here was already found. Skip.

  11. Step 11 / 12
    sorted
    -40-11-1203i14lo25hi
    fixed0want0

    Fix nums[3] = 0. Now find two values in the rest that sum to 0.

  12. Step 12 / 12
    sorted
    -40-11-1203i14lo25hi
    sum3want0

    1 + 2 = 3 > 0. nums[5] is too large; move hi left.

The closest sum to a target

If you're asked for the triple whose sum is closest to a target you keep the same loop and only the bookkeeping changes. You hold on to the best sum you've seen so far and on each step you move lo up when the sum's too small and hi down when it's too big, and if you hit the target exactly you can return straight away. The duplicates don't matter here because you only want one number back, though you'll still save a bit of time by skipping a fixed value you've already tried.

You can take the same idea further. For four values summing to a target you fix two values in nested loops and run one scan, which is O(n³), and for k values it's O(n^(k−1)). Once you're past three it's worth asking yourself whether a hash map of pair sums would be quicker for the sizes you've been given.

TimeO(n²)
SpaceO(1) extra

The sort is O(n log n), so it doesn't change the total. Some languages' sorts use O(log n) stack, which you can mention if they ask about space.

Problems in this module