Two Sum: One-Pass Hash Map, the Two-Pointer Variant, and the Follow-Ups That Get Asked

Two Sum is simple enough to expose whether a Software Engineer reads the contract before reaching for a memorized pattern. The core problem asks for two distinct elements whose values add to a target. The best solution depends on details that are easy to skip: whether the input is sorted, whether the output is indices or values, how ties are resolved, and what to return when no pair exists.

Start with the one-pass hash map for an unsorted array of indices. Then learn why it is correct, where its tie-breaking behavior comes from, and which follow-ups require a different data structure.

Clarify the contract before choosing an algorithm

Ask enough questions to make the output testable:

Contract detail	Why it changes the solution
Return indices, values, or a boolean?	Determines whether you need a map, set, or value-pair output
Is the input already sorted?	Makes an O(1)-space two-pointer scan possible
Is exactly one pair guaranteed?	Changes the no-solution path and test cases
May the same value appear twice?	Requires separate indices for a pair such as [3, 3]
Return any pair or a specific pair?	Tie-breaking can invalidate the standard early return
Return one pair or all unique pairs?	Changes duplicate handling and output size
Can arithmetic overflow the value type?	May require a wider type for the complement or sum

The brute-force baseline checks every pair (i, j) with i < j. It takes O(n²) time and O(1) extra space. State that baseline, then improve it. There is rarely value in implementing both unless the interviewer requests it.

The decision is about the contract, not a hierarchy where one technique is always better. Sorting an unsorted array costs O(n log n) and can lose original index order. A hash map uses O(n) memory but preserves the one-pass index relationship.

Prove the one-pass hash map

For each element x at index j, compute the needed value target - x. If that value has appeared at an earlier index, return the stored index and j. Otherwise store x for future elements.

def two_sum(nums, target):
    """Return two zero-based indices, or an empty list if no pair exists."""
    seen = {}
    for j, value in enumerate(nums):
        needed = target - value
        if needed in seen:
            return [seen[needed], j]
        if value not in seen:
            seen[value] = j
    return []

Check for the complement before inserting the current value. That order prevents one array position from matching itself. It still handles duplicates correctly: for [3, 3] and target 6, the first 3 is stored before the second 3 looks it up.

The loop invariant is precise: before processing index j, seen contains an earlier index for every value observed in nums[0:j]. If target - nums[j] is present, the two indices are distinct and their values sum to the target. If it is absent, no pair ending at j exists among the processed elements. After the final index, an empty result therefore means no pair exists.

Expected time is O(n), with O(n) extra space in the worst case. "Expected" reflects average hash-table lookup behavior. In a fixed-width language, compute target - value or value + other in a type wide enough for the input bounds.

The early return has a tie-breaking rule whether you intended one or not. It returns the valid pair with the earliest second index encountered by the scan. Preserving the first stored index for each value then gives the earliest matching first index for that second index. This is not necessarily the lexicographically smallest pair. For [1, 2, 4, 5] with target 6, the scan returns [1, 2], while [0, 3] is lexicographically smaller.

Use two pointers when order is part of the contract

For an already sorted array, place one pointer at each end. If the sum is too small, advance the left pointer. If it is too large, retreat the right pointer. On a match, record it and move past equal values if the output requires unique value pairs.

def unique_value_pairs(sorted_nums, target):
    """Return unique value pairs from an ascending array."""
    left, right = 0, len(sorted_nums) - 1
    pairs = []

    while left < right:
        total = sorted_nums[left] + sorted_nums[right]
        if total < target:
            left += 1
        elif total > target:
            right -= 1
        else:
            low, high = sorted_nums[left], sorted_nums[right]
            pairs.append((low, high))
            while left < right and sorted_nums[left] == low:
                left += 1
            while left < right and sorted_nums[right] == high:
                right -= 1

    return pairs

The discard argument is the proof. If sorted_nums[left] + sorted_nums[right] is below the target, pairing the left value with any remaining value cannot produce a larger sum than the current right endpoint. That left value cannot participate in a solution, so advancing it is safe. The symmetric argument applies when the sum is too large.

The scan takes O(n) time and O(1) extra space beyond its output. If you must sort first, total time becomes O(n log n). If original indices matter, sorting also requires index bookkeeping and may not be the best trade.

Do not confuse this pattern with sliding window. Two pointers here choose two positions whose values form a pair. A sliding window maintains a contiguous range and an invariant over every element inside it. The sliding-window guide shows that distinction with examples.

Re-derive the follow-up instead of forcing the base solution

One changed requirement can invalidate the standard hash-map answer:

Follow-up	Better representation	Why
Return only whether a pair exists	Hash set	No index needs to be stored
Return all unique value pairs from sorted input	Two pointers	Sorted order supports linear deduplication
Return the closest pair sum	Sort plus two pointers	There is no exact complement key to look up
Count pairs across two arrays	Frequency maps	Multiplicity becomes part of the answer
Support repeated updates and queries	Maintained frequency counters	Avoids rebuilding state after every update
Return the k smallest cross-array sums	Min-heap frontier	Avoids materializing the full pair grid
Require a special index tie-break	Contract-specific index structure or full scan	Early return may optimize the wrong index

For 3Sum, sort the array, fix one value, and run two pointers on the remaining suffix for the reduced target. Skip duplicates at the fixed value and after each pair match. This takes O(n²) time, which improves on enumerating every triplet, and uses O(1) auxiliary space beyond sorting and output under an in-place sort model.

For k smallest pairs from two sorted arrays, the pair sums form an implicit grid. A min-heap can keep only the current frontier. The Python heap guide covers the operations used in that design. A kth-smallest value variant may also support binary search on the answer when you can count how many pairs fall below a candidate sum.

Before finishing any variant, test duplicates, negative values, no solution, the smallest input, and multiple valid answers. Also state whether the algorithm mutates the input and whether output size dominates the claimed complexity.

The technical interview rubric guide can help you practice the surrounding explanation without guessing how a particular company scores a current round.

FAQ

Why do I check the complement before inserting the current value?

It guarantees the stored index is earlier than the current index, so one element cannot match itself. It still permits two equal values at different indices.

Is the one-pass hash map always O(n)?

It is O(n) expected time under average hash-table behavior and O(n) extra space. A fully deterministic worst-case guarantee requires a different map implementation or different assumptions.

Should I store the first or latest index for a repeated value?

For the usual "return any pair" contract, either can produce a valid answer if lookup happens before insertion. Keeping the first index makes the early-return tie behavior easier to state. A required global tie-break may need a different algorithm.

When is sorting better than a hash map?

Sorting is attractive when the input is already sorted, memory is constrained, output is based on values rather than original indices, or the task needs unique pairs or closest sums. On unsorted input where original indices matter, the hash map is usually the simpler O(n)-expected-time choice.

How does Two Sum become 3Sum?

Sort the values, fix one position, and solve a two-pointer Two Sum for the remaining target on the suffix. Repeat for each distinct fixed value while skipping duplicates.