parikshan

three-sum

Difficulty: Medium  ·  Topic: Two Pointers  ·  Practice it on parikshan: /practice/three-sum/start

The story

Goldman Sachs runs a daily delta-neutralisation report on its equity options book. For a given underlying, the desk has a list of net P&L contributions from individual positions. The risk team wants every unique triple of positions that, summed, exactly cancel out, those triples are the candidates for an end-of-day netting trade that flattens exposure for free. The list might be 3,000 positions long and duplicates are routine. The output must be deduplicated; you cannot report the same triple twice just because two of its values happened to repeat in the input.

That is three-sum. It is the canonical "k-sum collapsed to two pointers via sorting" problem, and once you have it in your fingers, four-sum, k-sum, and three-sum-closest are all the same skeleton.

What's actually being asked

Given an integer array nums, return every unique triplet (a, b, c) with a + b + c == 0. Each triplet is printed in non-decreasing order. The list of triplets is sorted lexicographically by the printed line (string compare of "a b c"). Duplicate triplets are forbidden.

The naive approach

Three nested loops over all i < j < k. Check if the sum is zero, dump matches into a set keyed by the sorted tuple, then print. O(n³) time. For n = 3,000 that is 27 billion iterations, hopelessly past the 3-second budget. Even in C++ you would lose.

The key insight

Sort the array first. Now fix the smallest element of the triplet at index i, and the rest of the problem becomes: find every pair (l, r) with l > i and nums[l] + nums[r] == -nums[i]. That is two-sum-ii-sorted on the suffix, which two pointers solves in linear time. Outer loop is O(n), inner two-pointer scan is O(n), total O(n²).

Three new concerns the sorted version forces on you:

  1. Skipping duplicate first elements. If nums[i] == nums[i-1], you have already enumerated every triplet that starts with this value. Skip i.
  2. Skipping duplicates after a hit. When (nums[i], nums[l], nums[r]) sums to zero, both l and r need to skip past any equal neighbours before the next iteration, or you will record the same triplet again.
  3. Early break when nums[i] > 0. Every element from i onward is positive (the array is sorted), so no triplet starting at i can sum to zero. Stop the outer loop.

The duplicate-skip rule is the part nobody gets right on the first try. Write it once, learn it forever.

Step-by-step approach

  1. Sort nums in non-decreasing order.
  2. For i from 0 to n - 3:
    • If nums[i] > 0, break. No triplet starting here can sum to zero.
    • If i > 0 and nums[i] == nums[i - 1], continue. Already covered.
    • Set l = i + 1, r = n - 1, need = -nums[i].
    • While l < r:
      • s = nums[l] + nums[r].
      • If s == need: record triplet (nums[i], nums[l], nums[r]). Then advance l past duplicates (while l < r and nums[l + 1] == nums[l]: l += 1) and decrement r past duplicates similarly. Finally l += 1, r -= 1.
      • If s < need: increment l.
      • If s > need: decrement r.
  3. Format each triplet as "a b c", sort the resulting list of strings, print one per line.

Worked example

nums = [-1, 0, 1, 2, -1, -4]

After sorting: [-4, -1, -1, 0, 1, 2].

  • i = 0, nums[i] = -4, need 4. l=1, r=5: sum -1+2=1<4, l++. l=2: -1+2=1<4, l++. l=3: 0+2=2<4, l++. l=4: 1+2=3<4, l++. Loop ends, no triplet.
  • i = 1, nums[i] = -1, need 1. l=2, r=5: -1+2=1, hit. Record (-1, -1, 2). Skip duplicates: nums[3] == 0 != -1, no skip on l; nums[4] == 1 != 2, no skip on r. l=3, r=4: 0+1=1, hit. Record (-1, 0, 1). l=4, r=3, loop ends.
  • i = 2, nums[i] = -1, but nums[1] == -1, skip.
  • i = 3, nums[i] = 0, need 0. l=4, r=5: 1+2=3>0, r--. l=4, r=4, loop ends.

Triplets: (-1, -1, 2) and (-1, 0, 1). Formatted lines: "-1 -1 2" and "-1 0 1". Sorted lexicographically the first stays first. Output matches the expected.

Complexity

  • Time: O(n²). Sorting is O(n log n); the outer loop is O(n) and each inner two-pointer pass is O(n).
  • Space: O(1) extra, ignoring the output list and sort overhead.

For n = 3,000 that is around 9 million ops; comfortably under the 3-second budget in Python.

Common pitfalls

  • Forgetting to sort. Without sorting, the duplicate-skip logic does not work and the two-pointer move rule is wrong.
  • Skipping duplicates before the hit instead of after. If nums[l] == nums[l + 1] you must still consider the current l. The skip happens after you have used the value.
  • Skipping i incorrectly. The guard is if i > 0 and nums[i] == nums[i - 1]. Skipping when nums[i] == nums[i + 1] is wrong; it kills the first occurrence.
  • Output sorted wrong. The spec asks for lexicographic by printed string, not by tuple-of-int. The difference shows up with negative numbers because '-' is less than digits. Build the strings, then sort the strings.
  • Stopping the outer loop at n - 1 instead of n - 3. You need at least two elements after i for the inner scan.

Where this shows up in the enterprise

  • Goldman Sachs / JPMorgan delta-neutralisation: find triples of positions that net to zero exposure for end-of-day flat trades.
  • Snowflake query optimiser: triple-join cost equality checks during plan enumeration.
  • Uber surge pricing: find triples of drivers whose combined supply matches a demand spike target.
  • Walmart distribution: triples of warehouse shipments that exactly fulfil a customer multi-item order without splitting.
  • Splunk / Datadog correlation: triples of log events that sum to a session signature (used in observability anomaly hunting).
  • YouTube ad auctions: triples of bids that hit a reserve sum, examined when the standard pair check fails.
  • CRISPR-edit screening at Genentech: triples of sgRNA scores that net to a target combined effect.
  • AWS Trusted Advisor: triples of compute reservations whose summed capacity exactly meets a workload spec.

The pattern is: pre-sort the candidate list, fix one anchor, run two pointers on the suffix. Any system that does "find me a small set of records that combine to a property" reaches for this shape.

Variants you'll see elsewhere

  • two-sum: hash-map version when the array is unsorted and only two elements matter.
  • two-sum-ii-sorted: the sub-routine three-sum reduces to.
  • three-sum-closest: same skeleton, the answer is the triplet closest to a target rather than equal to it.
  • four-sum: outer loops over two indices, two pointers on the remaining suffix. O(n³).
  • k-sum: recursive generalisation; base case is two-sum.
  • three-sum-with-multiplicity: count triples instead of enumerating, with multiplicity rules on duplicates.

How parikshan turns this into a learning loop

After you read this article and click through to the practice link, the parikshan flow integrates four layers:

  1. The editor runs your code against public tests for instant feedback and against per-session dynamic private tests (generated freshly per session). Synthetic cases for this problem hit the all-zeros input, heavy duplicates, the no-triplet branch, and outputs with hundreds of triplets to stress the sort step.
  2. Hints are graduated. Level 1 nudges toward sorting; level 4 gives you the full duplicate-skip recipe. Each level costs integrity points, so you choose deliberately.
  3. The AI training assistant in exam mode offers Explain, Review, Find Bugs, Add Comments, Optimise. Each costs integrity. In practice mode AI chat is free.
  4. The dispute flow runs after the verdict. The most common dispute on this problem is "my triplets are correct but the order is different". Read the spec carefully before disputing, the lexicographic-on-printed-string rule is precise.

Read this concept first, attempt the problem in practice mode, take a hint only when you genuinely need one, then redo it in exam mode with no help. When you can write the full duplicate-skip recipe from memory inside ten minutes, the pattern is in your fingers and you can interview at any "k-sum-and-its-variants" company on the planet.

In the AI-integrated workspace

In your future job, the agent writes the code. Your job is to:

  1. Recognise that any "find groups of k items that combine to a target" question collapses to sort-plus-pointer for k = 2 or 3, and to nested-loops-plus-pointer for k ≥ 4. That recognition is the entire skill.
  2. Tell the agent precisely: "sort, fix the smallest, two-pointer the rest, skip duplicates on i and on a hit, break on nums[i] > 0". Each clause is load-bearing; if the agent skips one, you get duplicates or extra work.
  3. Read the generated code and verify: the duplicate-skip happens after the hit, the outer loop has the early-break, and the output is sorted by printed string (not tuple).
  4. Push the edge cases the agent will miss: all zeros, all same negative, exactly three values, dense duplicates around zero like [-2, -2, 0, 0, 2, 2].

Candidates who can name "this is k-sum, do sort plus pointer" within five seconds are the ones who turn agents into leverage. Candidates who can't end up reviewing 80 lines of nested generated code with a Counter import and approve it because the public tests pass. parikshan is built to train the first kind.