parikshan

two-sum

Difficulty: Easy  ·  Topic: Arrays & Hashing  ·  Practice it on parikshan: /practice/two-sum/start

The story

A small fintech startup deduplicates incoming wire transfers. Each transfer has a unique reference number. The compliance team asks for a daily report: which pairs of transfers, on the same day, sum to a flagged round number (say $10,000, the legal threshold above which extra reporting kicks in)? They send you a list of amounts and the threshold. They want the indices of one such pair if it exists.

That is two-sum. Once you see this problem in this framing, you will spot it everywhere: which two open invoices add up to a stripe charge, which two click events sum to a session timing, which two log lines bracket a request.

What's actually being asked

Given an array of integers nums and an integer target, return the indices of two numbers in nums that add up to target. Exactly one such pair exists. You may not use the same index twice.

The naive approach

A nested loop. For each i, for each j > i, check if nums[i] + nums[j] == target. O(n²). For a list of 10,000 transfers, that is 50 million comparisons. For 1 million transfers, that is 500 billion. The naive answer is correct and useless.

The key insight

The inner loop is asking, for each i: "is target - nums[i] somewhere in the array?". That is a membership question. The right data structure for membership is a hash map. If you walk the array once, putting every value you've seen into a hash map (with its index as the value), each membership check is O(1) and the total is O(n).

There is only one subtle bit: a value cannot pair with itself unless it appears twice. So you check the map before you insert the current value. That ordering is the whole correctness argument.

Step-by-step approach

  1. Create an empty hash map seen from value to index.
  2. For each i from 0 to n-1:
    • Let complement = target - nums[i].
    • If complement is in seen, return [seen[complement], i]. Done.
    • Otherwise, store seen[nums[i]] = i.
  3. (Problem guarantees a solution exists, so the loop will return.)

Worked example

nums = [3, 7, 11, 2, 4]
target = 9
  • i=0, nums[i]=3, complement=6, seen={}, not found → seen={3:0}
  • i=1, nums[i]=7, complement=2, seen={3:0}, not found → seen={3:0, 7:1}
  • i=2, nums[i]=11, complement=-2, not found → seen={3:0, 7:1, 11:2}
  • i=3, nums[i]=2, complement=7, found! seen[7]=1, so return [1, 3].

Verify: nums[1] + nums[3] = 7 + 2 = 9. ✓

Complexity

  • Time: O(n), one pass.
  • Space: O(n), the hash map.

Compare to brute force: O(n²) time, O(1) space. The hashing solution trades constant memory for a quadratic-to-linear speedup. In a world where memory is cheap and clock cycles are expensive, that trade is always worth it.

Common pitfalls

  • Inserting before checking: if the array has duplicate values and the target is twice that value (e.g., [3,3], target=6), inserting first lets 3 match itself and you return [0, 0]. Wrong.
  • Returning values, not indices: the spec asks for indices. Read the spec.
  • Trying to sort first: sorting loses the original index, and you also burn an extra O(n log n). The two-sum-ii-sorted variant in this bank explicitly takes a sorted input; that is when sorting becomes acceptable.

Where this shows up in the enterprise

  • Stripe / Adyen reconciliation: matching payouts to refunds. Two ledger entries summing to zero, find them.
  • Bloomberg trade reconciliation: which buy and sell ticket on the same instrument net to zero exposure.
  • Splunk / Datadog log correlation: which two events have timestamps that bracket a request id.
  • Airbnb / Booking pricing experiments: which two discount slots, applied together, hit the target spend.
  • A/B test analysis: which two variant groups have post-stratification weights summing to 100%.
  • Inventory and supply chain: which two warehouse shipments combine to fulfil an order.
  • Compliance audit: the daily over-threshold-reporting check from the story above.

The pattern is universal: "two things that combine to a property". Once you see it, every problem that asks for two related items by a single property is a two-sum problem.

Variants you'll see elsewhere

  • two-sum-ii-sorted: sorted input, no hash map, O(1) extra space, two pointers.
  • three-sum: sort, fix one, two-pointer the rest. O(n²).
  • four-sum and k-sum: same idea, more pointers.
  • subarray-sum-equals-k: replace the array with prefix sums and you have two-sum on prefix sums.
  • two-sum-iii: design a data structure where add and find each have specified complexity.

The whole k-sum family is the same insight repeated.

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) so memorising someone else's solution is useless.
  2. Hints are graduated. Take the first hint and you sacrifice a few integrity points for one line of nudge ("what could you remember about previously seen numbers?"). Take the third hint and you get the full algorithmic skeleton, at a larger penalty. The integrity score is the platform's measure of independent thinking.
  3. The AI training assistant is a sparring partner, not an answer key. In exam mode, you can ask it to Explain the problem, Review your current code, Find Bugs, Add Comments, or Optimise. Each request docks integrity by a small amount, so the cost forces you to choose deliberately. In practice mode, AI chat is free-form and free of penalty: the place to learn the pattern at leisure.
  4. The dispute flow runs after the verdict. If you believe your solution is correct and the judge is wrong (every coder's instinct), one click sends the code to a human reviewer. The reviewer can override the verdict. This is the last layer of the loop and is what makes the score trustworthy.

Read the concept here, attempt the problem in practice mode first, accept the integrity hit only when you genuinely need a hint, then redo the problem in exam mode with no help. When you can solve it in exam mode in under five minutes without touching AI, the pattern is in your fingers.

In the AI-integrated workspace

In your future job, you will not write two-sum from scratch. An agent will. Your job is to:

  1. Recognise, when reading a feature spec, that an O(n²) approach is implicit and a hash-based O(n) approach is available. That recognition is the entire skill.
  2. Tell the agent precisely: "this is a two-sum pattern, use a hash map of previously-seen values".
  3. Read the agent's code and verify it checks the map before inserting.
  4. Stress-test on the edge cases the agent will silently miss: duplicates, empty input, negative numbers, a target that matches the same index twice.

Candidates who can name "this is two-sum" within five seconds of reading the spec are the ones who direct AI agents productively. Candidates who cannot recognise the pattern end up reviewing 50 lines of generated nested loops and approving them, because the tests pass on the sample. parikshan is built to train the first kind of candidate.

two-sum