cf.completefrontend
TWO POINTERS · CORE

K-sum (three or more items with a target sum)

Find groups of three or more items that add up to a target by fixing items one at a time and solving the last pair with two pointers.

Time O(n²)Space O(1) besides the output and the sort5 practice problemsStep-through picture

The idea

Finding a pair with a target sum in a sorted list takes one walk with two pointers. K-sum asks the same for three, four, or more items: which three items add up to zero, or which four widths fill a row exactly.

The trick is to reduce the problem. Sort the list. For three items, fix the first item nums[i] with a loop. Now you need a pair in the rest of the list that adds up to target - nums[i], and that is the two-pointer pair search. For four items, fix two items with two loops and search for the last pair.

Most k-sum questions want each group only once. Sorting puts equal values next to each other, so you can skip a value that is the same as the one before it. That stops you from building the same group twice.

An everyday example

Choosing three dishes for a fixed budget

A menu lists dishes from cheapest to most expensive, and you want three dishes that cost exactly your budget. You pick the first dish, then look for two more using the cheap end and the expensive end of the rest of the menu, moving inward. When that runs out, you pick the next first dish. If the next dish has the same price as the one you just tried, you skip it, because it would give the same price groups again.

How the example maps to the code
In the exampleIn the code
The first dish you picknums[i]
The cheapest and most expensive of the restnums[left] and nums[right]
The total of the three dishesnums[i] + nums[left] + nums[right]
Skipping a first dish with the same priceif (i > 0 && nums[i] === nums[i - 1]) continue
Writing down a group that fits the budgetresult.push([nums[i], nums[left], nums[right]])

From the slow way to k-sum (three or more items with a target sum)

  1. Start with the obvious way for three items: three nested loops over i < j < k, checking each triple's sum. For 1,000 numbers that is 166,167,000 triples. It is O(n^3), and on top of that, repeated values make the same group of numbers appear many times.
  2. Notice that fixing one item turns the problem into one you already know. Once nums[i] is chosen, you need two more items, after i, that add up to target - nums[i]. That is a pair-sum question.
  3. If the list is sorted, the pair-sum question is the two-pointer walk: left just after i, right at the end, moving inward by the usual rule. Each walk is O(n), and there are about n choices of i, so the whole search is O(n^2) instead of O(n^3).
  4. Sorting also solves the repeats, because equal values end up side by side. Skip an i whose value equals the previous i, and after saving a group, skip left past copies of the value just used. Sort, fix the first item, walk the pair, skip repeats: that loop is k-sum.

How it works

  1. Sort nums in ascending order.
  2. Loop i over every index that leaves room for two more items. This fixes the first item.
  3. If nums[i] equals nums[i - 1], skip it: every group starting with that value was already found.
  4. Set left = i + 1 and right to the last index, then do the two-pointer walk on the part after i.
  5. If the three items add up to less than target, move left right; if more, move right left.
  6. If they add up to target, save the group, move both pointers inward, and skip values equal to the one just used at left.
  7. After every i is done, return all saved groups.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function threeSum(nums, target) {
  2. nums.sort((a, b) => a - b);
  3. const result = [];
  4. for (let i = 0; i < nums.length - 2; i++) {
  5. if (i > 0 && nums[i] === nums[i - 1]) continue;
  6. let left = i + 1;
  7. let right = nums.length - 1;
  8. while (left < right) {
  9. const sum = nums[i] + nums[left] + nums[right];
  10. if (sum < target) {
  11. left++;
  12. } else if (sum > target) {
  13. right--;
  14. } else {
  15. result.push([nums[i], nums[left], nums[right]]);
  16. left++;
  17. right--;
  18. while (left < right && nums[left] === nums[left - 1]) left++;
  19. }
  20. }
  21. }
  22. return result;
  23. }

How fast it is

TimeO(n²)
Extra memoryO(1) besides the output and the sort

The outer loop runs n times and each pair walk is at most n steps. Sorting is O(n log n), which is smaller. The groups found are the only real memory used.

  • Best caseO(n log n)

    All values equal, like 1,000 zeros: the sort dominates. The first walk saves [0, 0, 0] and moves left to the end, and every later i is skipped as a repeat. In one test this took about 2,000 loop steps.

  • Average caseO(n^2)

    Mostly distinct values: about n walks of up to n steps each. In one test with 1,000 distinct values, the loops took about 375,000 steps.

  • Worst caseO(n^2)

    Distinct values with few or no answers: every i gets a full walk until the pointers meet.

Common mistakes

  • Forgetting to skip repeated values, which saves the same group many times, such as [-1, 0, 1] twice.
  • Calling nums.sort() with no compare function, which sorts numbers as text: [-1, -4, 0] stays in a wrong order.
  • After finding a group, moving only one pointer. The other pointer's item now needs a different partner, so the loop finds nothing new or repeats the group.
  • Using a Set of joined strings to remove repeat groups. It works but hides the real fix and uses extra memory; sorting and skipping is cleaner.

When to use it

Look for these clues in a problem:

  • The question asks for three or four items whose sum equals, comes closest to, or stays below a target.
  • It asks for all such groups, each listed once, so duplicates must be skipped.
  • The order of the input doesn't matter for the answer, so sorting is allowed.
  • An O(n³) or O(n⁴) loop over every group is too slow, but O(n²) is fine.

Check yourself

Answer each one in your head first, then open it.

Why does the outer loop stop at nums.length - 2?

left starts at i + 1 and must be less than right, the last index, so i needs at least two items after it. The last useful i is nums.length - 3.

Why is skipping an i equal to nums[i - 1] safe?

The walk for i - 1 searched every item from i on, a superset of what i would search. Any group starting with that value was already found.

Why don't you need to skip copies at right after a save?

After left moves past every copy of its value, the new nums[left] is different, so the partner that makes the same sum must be different too. A repeat group can't form.

How many steps does the search take for 4 numbers?

At most 2 walks (i = 0 and i = 1), with at most 2 and 1 pointer steps, so 3 steps plus the sort. The O(n^2) growth shows only for bigger inputs.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Every answer group, written in sorted order, has a smallest index i, and its other two items come after i. So if, for each i, the pair walk finds every pair after i that adds up to target - nums[i], the outer loop finds every group. The walk does exactly that, by the same proof as the two-pointer pair search: each pointer move only drops an item that can't be in any pair with the current nums[i].

Skipping an i whose value equals nums[i - 1] loses nothing. The walk for i - 1 searched the items from i on, which include every item after i, so it already found every group that starts with that value. The same reasoning covers moving left past copies after a save: a second group with the same nums[left] value would need the same partner, so it would be the same group.

Everything ends: each walk moves a pointer inward every step, so it stops after at most n steps, and the outer loop visits each i once. When the outer loop ends, every possible smallest index has been tried, so result holds every group exactly once.

Going deeper

3 more ideas

Why fixing one item turns it into a pair search

Every group of three has a smallest index i. Once nums[i] is fixed, the other two items come from the part after i, and they must add up to target - nums[i]. That part is still sorted, so the two-pointer walk finds every pair with that sum in one pass. Trying every i therefore tries every group.

Why it takes O(n²) time

Sorting costs O(n log n). The outer loop runs about n times, and each two-pointer walk takes at most n steps, so the total is O(n²). For four items, there are two fixed loops and the walk, so O(n³). Each extra item adds one loop, so k-sum takes O(n^(k-1)).

Skipping duplicates in the right places

There are two places that can create a repeated group. The first item: skip i when nums[i] === nums[i - 1]. The pair: after saving a group, move left past every copy of the value just used. You don't need a third skip for right, because once nums[left] changes, the matching nums[right] must change too.

Work it by hand

Every step in a table, with why

Find every group of three that adds up to 0. After sorting, the value -3 appears twice, so one i is skipped.

nums = [5, -3, 1, -3, 2, 0, -2], target = 0; sorted: [-3, -3, -2, 0, 1, 2, 5]

Stepi (nums[i])leftrightsumWhat happensWhy
10 (-3)16-1Too small: left++-3 + -3 + 5 = -1. A bigger middle item is needed.
20 (-3)260Save [-3, -2, 5], move bothA match. Both pointers move inward, to left = 3 and right = 5.
30 (-3)35-1Too small: left++-3 + 0 + 2 = -1.
40 (-3)450Save [-3, 1, 2], move bothAnother match. Now left = 5 and right = 4, so this walk ends.
51 (-3)---Same as nums[0]: skipEvery group starting with -3 was already found when i was 0, so this i is skipped.
62 (-2)363Too big: right---2 + 0 + 5 = 3. A smaller last item is needed.
72 (-2)350Save [-2, 0, 2], move bothA match. Both pointers move to 4, so this walk ends.
83 (0)466Too big: right--0 + 1 + 5 = 6.
93 (0)453Too big: right--0 + 1 + 2 = 3, still too big. The pointers meet and the walk ends.
104 (1)568Too big: right--1 + 2 + 5 = 8. This is the last i, because i < nums.length - 2 means i stops at 4.

It returns [[-3, -2, 5], [-3, 1, 2], [-2, 0, 2]]. The outer loop ends at i = 4, the last index that leaves room for left and right.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
K-sum (three or more items with a target sum)O(n^2)O(1)You need every group of three once, or the closest sum, and sorting the input is allowed.
Three nested loopsO(n^3)O(1)n is at most a few hundred, or you want a slow reference to test the fast version against.
Fixed item plus a hash setO(n^2)O(n)Sorting isn't allowed or you need original positions; removing repeat groups then needs extra care.

Extra memory: O(1) beyond the output and the sort. JavaScript's sort may use O(n) memory of its own, and the output can hold up to O(n^2) groups.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for K-sum (three or more items with a target sum) and the other approaches, on a scale where each line up is 10 times more steps.
  • K-sum (three or more items with a target sum), Fixed item plus a hash set O(n^2)
  • Three nested loops O(n^3)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
K-sum (three or more items with a target sum)1001 million1 trillion
Three nested loops1,0001 billionmore than a quadrillion
Fixed item plus a hash set1001 million1 trillion

Inputs that need care

5 tricky inputs
Fewer than three numbers: nums = [1, 2]
i < nums.length - 2 is false at once, so it returns [].
All zeros: nums = [0, 0, 0, 0]
It returns [[0, 0, 0]] once. The skip after a save moves left past every extra zero, and later i values are skipped as repeats.
No group works: nums = [1, 2, 3, 4], target = 100
Every walk moves left until the pointers meet, and the result is [].
Sorting without a compare function
[10, 9, -1, -4].sort() gives [-1, -4, 10, 9], because it compares text. The two-pointer rule then moves the wrong way. Always pass (a, b) => a - b.
The caller's array changes
nums.sort sorts in place, so the caller's array comes back reordered: [3, -1, -2] becomes [-2, -1, 3]. Sort a copy, [...nums].sort((a, b) => a - b), if that matters.

Variations and follow-ups

Twists interviewers add

Closest sum of three

Keep the sum with the smallest Math.abs(sum - target) instead of saving matches, and move the pointers by the same rule. Duplicate skipping becomes optional, because only one number is returned.

Four or more items

For four items, add another fixed loop: i, then j > i, then the pair walk, which is O(n^3). A general version fixes one item and calls itself with k - 1 and the remaining target, ending at the two-pointer walk when k is 2. Each extra item adds a factor of n.

Counting triples below a target

When nums[i] + nums[left] + nums[right] < target, every index from left + 1 to right also works with nums[i] and nums[left], so add right - left at once and move left. This counts in O(n^2) without listing the triples.

A hash set for the pair

For each i, scan the items after it and look up target - nums[i] - nums[j] in a Set of values seen so far in that scan. It is also O(n^2) but uses O(n) extra memory, and avoiding repeated groups is harder without sorting.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "three (or four) numbers that add up to", "all unique groups", or "closest sum of three". If the input order doesn't matter, sorting is the first move.
  • Explain the reduction out loud: "I fix the smallest item with a loop, and the rest is a pair-sum search on the sorted part after it, which two pointers solve in O(n)."
  • Spend extra care on repeats: say where the two skips go and why there is no third skip for right. Then test by hand with all zeros and with a value that appears twice as a first item.
  • Expect the follow-up "what about four numbers, or k?". The answer: one more fixed loop per extra item, or a recursive function that reduces k by one until it reaches the pair walk, for O(n^(k-1)) time.

Where frontend code uses it

The same idea in real UI code
  • A layout tool that picks three column widths to fill a fixed row width exactly can search widths with a fixed first width and a two-pointer pair.
  • A shop's bundle builder that suggests three products whose total price is closest to a gift card amount.
  • Checking a design system's spacing scale for three tokens that add up to a container's padding or gap.

Related algorithms