K-Sum

What is this?

You are given a stack of price tags and asked whether any three of them total exactly £100. Checking every combination is hopeless by hand. But sort them into a line, put a finger at each end, and the problem becomes tractable: if the pair in front of you is too cheap, the only way to improve is to slide the left finger up; too expensive, slide the right finger down. You never backtrack, and you never consider a combination twice.

The k-sum family is that trick with one or two prices held fixed while your fingers work on the rest.

💡 Fun fact: the general k-sum problem is 3SUM-hard — a whole complexity class is named after it. For decades it was conjectured that 3Sum could not be solved faster than O(n²), and although slightly sub-quadratic algorithms now exist, they are theoretical curiosities. The O(n²) you are asked to produce in an interview is, for practical purposes, the best known answer.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: every problem here is sort → fix k − 2 values → converge two pointers. Only the objective changes: an exact hit records a result, a near miss updates a best-so-far, and a bound counts a whole block at once.

1. The template

nums.sort()
for i in range(len(nums) - 2):
    if i > 0 and nums[i] == nums[i - 1]:
        continue                      # skip duplicate anchors
    left, right = i + 1, len(nums) - 1
    while left < right:
        total = nums[i] + nums[left] + nums[right]
        if total < target:
            left += 1
        elif total > target:
            right -= 1
        else:
            record(i, left, right)
            left += 1
            right -= 1
            while left < right and nums[left] == nums[left - 1]:
                left += 1             # skip duplicate lefts
            while left < right and nums[right] == nums[right + 1]:
                right -= 1            # skip duplicate rights

There are three duplicate skips, and all three are required. The anchor skip stops the same triple being found from a repeated first element; the left and right skips stop it being found again within the same sweep. Most buggy submissions have one or two of the three.

The objective is the only thing that varies:

2. Why right − left counts a whole block

For 3Sum Smaller, once nums[i] + nums[left] + nums[right] < target, every element strictly between left and right is at most nums[right] — so pairing any of them with left also stays under the target. That is right − left valid triples in one step.

sorted: [-2, 0, 1, 3],  target = 2,  anchor i = 0 (value -2)

left=1 (0), right=3 (3):  -2 + 0 + 3 = 1 < 2
                          → every j in (1, 3] works with left=1
                          → add right - left = 2   [(-2,0,1), (-2,0,3)]
                          → left = 2
left=2 (1), right=3 (3):  -2 + 1 + 3 = 2, not < 2  → right = 2, loop ends
                                                     count = 2

Incrementing one at a time would still be correct, just quadratically slower inside an already quadratic loop.

3. Where you'll actually meet this

• Financial reconciliation. "Which combination of these line items accounts for the discrepancy?" is subset-sum in general, but the fixed-size version is exactly this.
• Bundling and pricing. Finding a set of k items closest to a budget — the 3Sum Closest objective — is how "build a bundle near £50" features are implemented.
• Chemistry and bioinformatics. Mass-spectrometry peak matching looks for combinations of fragment masses summing to an observed total, within a tolerance.
• Resource packing. Choosing k machines whose combined capacity most nearly meets a request, without going under.
• Deduplication in analytics. The duplicate-skipping discipline here is the same care required whenever you report distinct combinations from a multiset.

4. Problems in this chapter

▶ 3Sum

Find all unique triples summing to zero. The archetype — and the duplicate handling, not the pointer walk, is what separates a passing answer from a correct one.
Pattern: sort + anchor + converge. Target: O(n²) time, O(1) extra space.

▶ 3Sum Closest

Return the triple sum nearest the target. Same sweep, different bookkeeping: track the best absolute difference, and keep moving on the sign of the current difference.
Pattern: converge, track best-so-far. Target: O(n²) time, O(1) space.

▶ 3Sum Smaller

Count triples summing to strictly less than the target. The batching insight — add right − left in one step — is the entire problem.
Pattern: converge, count in blocks. Target: O(n²) time, O(1) space.

▶ 4Sum

All unique quadruples summing to the target. Two nested anchors around the same converging pair, with duplicate skips at both anchor levels, plus overflow care in fixed-width languages.
Pattern: two anchors + converge. Target: O(n³) time, O(1) space.

5. Common pitfalls 🚫

• Skipping duplicates in only one place. All three skips are needed: the anchor, the left after a hit, and the right after a hit.
• Skipping the anchor with i instead of i > 0 and …. Comparing nums[i] == nums[i+1] and skipping forward drops legitimate triples where the anchor value genuinely repeats.
• Deduping with a set of tuples. It works and it is what interviewers expect you to outgrow — say why the skip-based version is better (no hashing of results, no extra space).
• Stepping one at a time in the counting variant instead of adding right − left.
• Moving only one pointer after an exact hit. The other end must move too, or the loop finds the same pair forever.
• Integer overflow in 4Sum. Four values near 10⁹ exceed a 32-bit int; use 64-bit outside Python.
• Forgetting that sorting destroys original indices. If the problem wants indices rather than values, this whole approach is wrong — that is a hash-map problem instead.

6. Key takeaways

1. Sort first — that is the algorithm, not setup. Order is what makes each pointer move provably safe.
2. One template, four objectives. Fix k − 2, converge over the rest, and change only what happens at the comparison.
3. Three duplicate skips, every time, or you will emit repeats.
4. Count in blocks, not steps when the objective is "how many below the bound".
5. k-sum costs O(n^(k−1)) — 3Sum is quadratic, 4Sum cubic — because each extra anchor adds a loop.
6. If the answer needs original indices, abandon this pattern. Sorting has thrown that information away; use a hash map.

Order: 3Sum → 3Sum Closest → 3Sum Smaller → 4Sum.