</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

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.

K-Sum core loop: sort, fix k-2 indices, converge left/right, compare against target with left++/right--/record branches looping back

Fun fact: 3Sum gave its name to a whole family of problems called 3SUM-hard. For decades it was conjectured that 3Sum could not be solved faster than O(n²). Slightly sub-quadratic algorithms now exist, but they are theoretical curiosities, and the O(n²) you are asked to produce in an interview is the answer people actually use.

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


In short: 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. A submission that has only one or two of them still emits repeats.

The objective is the only thing that varies:

Problem Inside the loop
exact sum record the triple, step both, skip duplicates
closest to target track min(abs(total − target)); still move on the sign of the difference
count below target when total < target, add right − left and left++
four numbers wrap the whole thing in a second anchor loop

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. (Check the boundary: a sum equal to the target does not count, so the test is strictly <.)

Trace showing why right - left counts a whole block: sorted [-2,0,1,3], target 2, anchor -2, yielding 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. Picking k items whose total lands closest to a budget is the 3Sum Closest objective. For small k and a small catalogue the sorted sweep is a direct fit.
  • Resource packing. Choosing k machines whose combined capacity meets a request with the least waste is the closest-sum objective (with the extra rule of not 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. 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 beyond the output and the sort.

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) extra space beyond the sort.

3Sum Smaller

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

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) extra space beyond the output and the sort. The lesson also shows a recursive k-Sum version that costs O(n) 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 and no set of triples held in memory.
  • 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. It 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 and 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.

3Sum Smaller

Core idea: Sort the array once, then fix one number and let two pointers, left and right, sweep the remaining slice. We are counting, not listing. The moment a fixed i plus the largest pair (left, right) lands strictly under the target, every pair between left and right is also under it, so we add all right - left of them in one O(1) step instead of inspecting each one.


Problem, rephrased

A cost dashboard prices three-resource bundles for finance. You're given an integer array nums, where nums[i] is the price of the i-th cloud resource (credits make some values negative), and an integer target, the budget line a bundle must stay under.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.