Two Number Sum

Problem Statement

You're given a list of integers and a target value. Find the two numbers in the list that add up to the target, and print their values (not their positions) in the order they appear when reading the list from left to right. The input is always set up so that exactly one such pair exists, so you never have to decide between multiple valid answers.

Input Format

The input has exactly two lines:

• Line 1: the array, as space-separated integers (at least 2 values).
• Line 2: a single integer, the target sum.

Output Format

Print the two matching values on one line, separated by a single space. Print the value that appears earlier in the array first, followed by the value that appears later.

Example Walkthrough

Take the sample array 5 12 3 8 19 with target 20. We scan the array from left to right while keeping track of the numbers we've already seen. At index 0 we see 5; its complement 20 - 5 = 15 hasn't been seen (nothing has), so we remember 5 and move on. At index 1 we see 12; the complement 20 - 12 = 8 isn't in the set either, so we remember 12. At index 2 we see 3; the complement 17 isn't in the set, so we remember 3. At index 3 we see 8; we check whether 20 - 8 = 12 has already been seen — it has, from index 1 — so we've found our pair. Because the problem guarantees exactly one valid pair exists, we don't need to look at index 4 (19) at all. We print the number that was seen first, then the current one: 12 8.

Approach

The slow way to solve this is to compare every pair of numbers in the array, which takes O(n²) time since for each number you'd scan the rest of the array looking for its complement. That works, but it does far more comparisons than necessary, especially on a large array.

A faster way is to make a single pass through the array while keeping a hash set of numbers you've already visited. For each number you encounter, first compute its complement — the value that, added to the current number, gives the target — and check whether that complement is already in your set. If it is, you've found your answer: the complement was seen at an earlier position, and the current number is at a later position, so printing them in that order automatically satisfies "earlier index first." If the complement isn't in the set yet, add the current number to the set and keep scanning.

This works in one pass because a hash set gives you an O(1) average-time way to ask "have I seen this value before?" instead of re-scanning the array. Since the problem guarantees exactly one valid pair exists, the first match your scan finds is the only match — you can stop as soon as you find it, and you never need to worry about which of several possible pairs to report.

Common Mistakes

• Using a nested loop to check every pair. It produces a correct answer, but its O(n²) time cost is exactly what the hash-set approach is meant to avoid — on a large array this pattern is far slower than necessary and is a common giveaway that the intended technique wasn't used.
• Printing the numbers in the wrong order. The number that was already in the hash set (the earlier index) must be printed first, and the number currently being processed (the later index) second — printing them in the order you happen to compute them, rather than the order their indices appear in the array, gives the wrong output even when the two values themselves are correct.
• Checking the hash set after inserting the current number instead of before. If you add the current number to the set and only then check for its complement, a number can incorrectly appear to pair with itself at the same position — this matters most when the matching pair happens to be two equal values, like 5 and 5, since the current 5 would find itself in the set.