Two Sum

Introduction

Two Sum is the most-asked coding interview question on Earth. That fact alone would earn it a chapter. But Two Sum deserves far more than that: it is where most engineers first learn the single most important performance lever in the entire coding-interview discipline — trading space for time using a hash table.

In the forty-five minutes of a typical on-site, the interviewer is really testing two things. Can you produce correct code? And: can you reason about tradeoffs? Two Sum surfaces both, fast. A candidate who writes only the nested loop reveals a ceiling. One who sees the $O(n)$ hashing solution but cannot explain why they look up before they insert reveals another. One who can produce the hashing solution, a sorted two-pointer alternative, and can argue when each wins — that candidate is already distinguishing themselves.

The skill Two Sum actually tests is not “can you do Two Sum”. It is “can you replace a search with a lookup, and know why it is safe.”

This chapter is designed to take you all the way there. If you are new to interview prep, read it linearly: the approaches, the narration, the traps. If you have written the hash solution a dozen times, jump to the Follow-ups and Correctness invariants sections — there is more nuance here than the typical problem sheet reveals.

What the interviewer is actually testing

Before we look at code, know what you are being graded on. The Two Sum rubric at most top companies scores four things:

1. Clarification discipline. Did you ask at least two sharp clarifying questions in the first minute?
2. Multiple approaches. Did you surface at least two qualitatively different solutions?
3. Tradeoff articulation. Can you argue which solution you would ship, and under what constraints you would switch?
4. Clean code. Did you write compilable, idiomatic code, and walk through it on a concrete input?

Every section below is organized around delivering those four signals.

Problem statement

Clarifying questions — and why each one matters

In the interview the problem will arrive slightly under-specified. Your clarifications are themselves being evaluated; asking the right ones in the first sixty seconds is one of the highest-value minutes of the whole session. Here is what to ask, and why.

A mental framework for lookup-shaped array problems

Before diving into approaches, here is the mental sequence I recommend for problems of this shape. It generalizes to 3Sum, 4Sum, Two Difference, Subarray Sum Equals K, Longest Substring Without Repeating Characters, and many more:

1. Enumerate and check. Can you brute-force every candidate? Write it as a baseline — even if you throw it away.
2. Exploit structure. Is the input sorted? Bounded in range? Non-negative? Structure is almost always the path to a better algorithm.
3. Replace search with a hash lookup. If the inner loop is looking for a specific value, a hash table collapses it to $O(1)$.
4. Replace search with sort + two pointers. If the inner loop is looking for a range of values, sort + two pointers is often simpler than hashing.
5. Replace recomputation with running state. Prefix sums, sliding windows, monotonic stacks.

For Two Sum, steps 1, 3, and 4 all apply. Let’s walk them.

Discussion

#include <vector>

// Returns true iff any two distinct indices i, j have A[i] + A[j] == T.
// O(n²) time, O(1) extra space. Use only as a baseline.
bool twoSum(const std::vector<int>& A, int T) {
    const int n = static_cast<int>(A.size());
    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (A[i] + A[j] == T) return true;
        }
    }
    return false;
}

#include <unordered_set>
#include <vector>

bool twoSum(const std::vector<int>& A, int T) {
    std::unordered_set<int> seen;
    seen.reserve(A.size());

    for (int x : A) {
        // CRITICAL: look for the complement BEFORE inserting x,
        // so x can never pair with itself when T == 2·x.
        if (seen.count(T - x)) return true;
        seen.insert(x);
    }
    return false;
}

#include <unordered_map>
#include <vector>

// Returns the zero-based indices {i, j} of any valid pair, or {-1, -1} if none.
// O(n) time, O(n) space.
std::pair<int, int> twoSumIndices(const std::vector<int>& A, int T) {
    std::unordered_map<int, int> idx; // value -> index of first occurrence
    idx.reserve(A.size());

    for (int i = 0; i < static_cast<int>(A.size()); ++i) {
        const int complement = T - A[i];
        auto it = idx.find(complement);
        if (it != idx.end()) {
            return {it->second, i};
        }
        // Insert only after the lookup — never overwrites an earlier occurrence.
        idx.emplace(A[i], i);
    }
    return {-1, -1};
}

#include <algorithm>
#include <vector>

// If the input is already sorted, skip the std::sort and this is O(n) / O(1).
// Otherwise O(n log n) / O(1).
// If the caller needs A to remain untouched, sort a copy.
bool twoSum(std::vector<int> A, int T) {
    std::sort(A.begin(), A.end());

    int lo = 0;
    int hi = static_cast<int>(A.size()) - 1;

    while (lo < hi) {
        const int s = A[lo] + A[hi];
        if (s == T) return true;
        if (s < T) ++lo;  // Sum too small: the only way to grow it is to raise the left.
        else       --hi;  // Sum too large: the only way to shrink it is to lower the right.
    }
    return false;
}

Approach comparison

Default answer for an unsorted input: hashing. Default for a sorted input: two pointers. Default when memory is tight: two pointers. Say this out loud when you close.

Follow-ups to anticipate

Pattern recognition — the real lesson

The move you learned here — replace an inner search with a hash lookup — is the single most productive pattern in the early-round array portion of coding interviews. It reappears constantly:

• 3Sum, 4Sum. Fix $k - 2$ elements, reduce to Two Sum.
• Subarray Sum Equals K. Hash prefix sums; look up prefix − K.
• Contains Duplicate. Hash each element; check before insert.
• Group Anagrams. Hash by a canonical key (sorted string).
• Longest Substring Without Repeating Characters. Hash last-seen position.
• Valid Sudoku. Hash sets per row, column, and box.

Once you see the shape — “at each element, I need to ask a lookup question about previous elements” — you apply the move on reflex. That reflex is what Two Sum is really teaching.

What to say out loud — the delivery script

Delivery is scored. Here is the narrative arc to rehearse:

1. Repeat the problem in your own words. “So I have an array of integers and a target; I need to decide whether any two distinct elements sum to the target.”
2. Ask the three clarifying questions. (See above.)
3. State the brute force + its complexity. “The obvious approach is two nested loops, $O(n^2)$. Let me write that as a baseline.”
4. Announce the insight. “I think I can do better by rearranging the equation. $a_j = T - a_i$. If I’ve seen $a_i$ before, I can look it up in a hash set in constant time.”
5. Write the code. No more than a dozen lines.
6. Walk through an example. Pick one of the given examples; trace the hash set filling.
7. State the look-before-insert invariant. “One trap here: you have to check the set before inserting $a_i$, otherwise $T = 2 \cdot a_i$ will false-positive.”
8. Call out edge cases. Empty array, single element, $T = 2 \cdot$ some element.
9. Mention the alternative. “If the input were sorted or we couldn’t allocate memory, I’d switch to two pointers after a sort.”
10. Summarize. “I’d ship the hashing version unless $O(1)$ space is required.”

Rehearse this until it’s automatic. The candidates who get offers aren’t the ones with the cleverest code — they’re the ones whose interview feels organized.

Summary

Two Sum looks like one problem. It is really three: the brute force is a warm-up, the hashing solution is the workhorse, the two-pointer solution is the connoisseur’s answer. Know all three, know when to use each, know the invariant that makes each one correct, and know what to say as you are writing them.

The problem is also a pattern detector. Every time an interview problem asks you to find something in an array where the criterion is “relative to some other element”, the Two Sum move — hash the values, look up the complement — is your first instinct. Internalize it here; it will save you on dozens of problems after.