Two Sum

Two Sum

What is this problem about?

"Two Sum" is widely regarded as the entry point into the world of technical interviews. You are given an array of integers nums and a target value. The challenge is to find the indices of the two numbers in the array that sum up exactly to the target. It's a fundamental problem that tests your ability to optimize search operations and manage data mapping efficiently. In the professional world, this is a basic pattern used in data lookup and financial reconciliation.

Why is this asked in interviews?

This "Two Sum interview question" is legendary, asked by nearly every major tech company from Google to Amazon. It's used as a "smoke test" to see if a candidate understands the most basic space-time trade-off. While the $O(N^2)$ brute-force solution is obvious, the real test is seeing if you can implement the $O(N)$ hash-map-based solution. It's also a great way to start a conversation about language-specific implementation details of hash tables (like hash collisions and amortized complexity).

Algorithmic pattern used

The "Array, Hash Table interview pattern" is the gold standard for this problem. You traverse the array once, and for each number, you calculate its "complement" (Target - Current). If this complement is already in your hash map, you have found the pair. If not, you store the current number's value and its index in the map for future lookups. This allows you to achieve linear time complexity at the cost of linear space complexity.

Example explanation

Target = 10. Array = [3, 5, 2, 7].

1. See 3: Need 7. Is 7 in the map? No. Map = {3: 0}.
2. See 5: Need 5. Is 5 in the map? No. Map = {3: 0, 5: 1}.
3. See 2: Need 8. Is 8 in the map? No. Map = {3: 0, 5: 1, 2: 2}.
4. See 7: Need 3. Is 3 in the map? YES! Index 0. Result: [0, 3].

Common mistakes candidates make

One common mistake is using the same element twice (e.g., if target is 10 and you have a 5, returning the index of 5 twice). Another error is returning values instead of indices. Some candidates also try to sort the array first, which takes $O(N \log N)$ and complicates the process of tracking the original indices, when the hash map approach is simpler and faster.

Interview preparation tip

For the "Two Sum coding problem," practice explaining the time and space complexity clearly. Be ready for follow-ups like "What if the array is already sorted?" or "What if you can't use extra space?" This shows you understand the problem from multiple architectural perspectives.