Solving Lookup and Pair-Finding Problems with Dictionaries and Sets

Hello! Last time, you solved one-pass problems by keeping a small summary of earlier items. The cheapest earlier price was enough to evaluate a sale, for example. This lesson handles a different situation: the answer may depend on whether you have seen a specific value before. A dictionary or set lets you retain that searchable history while still scanning the input once.

You’ll use that idea to find two numbers that add up to a target. The important choices are what to look up, what to store, and whether to look up before or after storing the current item.

Turn a pair search into a lookup

Suppose nums = [4, 5, 3, 2] and target = 6. You want two elements at different indices whose sum is $6$. If the problem asks for indices, the answer is [0, 3], because nums[0] + nums[3] is $4+2$.

A direct solution checks every pair. For each index, it compares that value with values at later indices. This uses $O(n^2)$ time in the worst case and $O(1)$ auxiliary space. To improve it, change the question you ask at each position. For a current value x, there is only one value that could complete the pair: target - x, called its complement.

Rather than search the rest of the list for that complement, keep a dictionary of values already encountered. At each position, ask whether the complement is in the dictionary. Python dictionary membership checks take $O(1)$ time on average.

Watch NeetCode’s Two Sum - Leetcode 1 - HashMap - Python. The first part establishes why checking every pair is costly; the rest develops the one-pass dictionary and shows its Python implementation.

The diagram below traces our example. The “Hash Table” column shows the dictionary before each lookup: each stored value points to an earlier index. At the final value, 2, its complement is 4, which is already stored at index 0.

Store values when the answer requires indices

When you must return positions, a set cannot tell you where an earlier value occurred. Use a dictionary whose keys are values and whose stored data are indices:

def two_sum_indices(nums, target):
    earlier_index = {}

    for index, value in enumerate(nums):
        complement = target - value

        if complement in earlier_index:
            return [earlier_index[complement], index]

        earlier_index[value] = index

    return None

Here, None means no pair exists. Some versions of Two Sum guarantee exactly one answer, in which case the final return is never reached; other versions specify a different no-answer result. Always follow the problem’s return contract.

The loop has a precise running-state rule: just before processing index i, earlier_index contains values from indices strictly less than i, with an earlier index for each stored value. Thus, a successful lookup gives you a different element, not the current one.

That rule explains the order of the two lines inside the loop. Consider nums = [3, 2, 4] with target 6. At index 0, the complement of 3 is also 3. The empty dictionary correctly says there is no earlier 3. If you inserted the current 3 before checking, you could incorrectly return [0, 0]. With nums = [3, 3], however, the second 3 finds the first one and correctly returns [0, 1]. Equal values are allowed; reusing the same index is not.

Why can a scan that looks only backward find a pair whose second member is still ahead? If a valid pair occurs at indices i and j, with i < j, its first value is stored when the scan passes i. When the scan reaches j, the first value is already available for lookup. The algorithm might return another valid pair sooner, but it cannot miss all valid pairs.

One Python detail matters when an index could be zero. Use if complement in earlier_index:, not if earlier_index.get(complement):. A found index of 0 is false in a Boolean test, even though it is a perfectly valid answer.

The loop performs one average-$O(1)$ dictionary lookup and at most one insertion per element. Its expected time is $O(n)$, and the dictionary can hold up to $n$ values, giving $O(n)$ auxiliary space. Unlike last lesson’s two-variable running state, this solution spends extra memory to make specific earlier values searchable.

Use a set when you need the values, not their positions

Now change the requested output: return any pair of values summing to the target, or an empty list if no pair exists. You no longer need to remember indices. A set of earlier values is enough.

GeeksforGeeks’ 2 Sum - Find a pair with given sum presents this version. Its page includes several approaches and programming languages; read only the indicated hash-set material.

In Python, that version can be written compactly:

def two_sum_values(nums, target):
    seen = set()

    for value in nums:
        complement = target - value

        if complement in seen:
            return [complement, value]

        seen.add(value)

    return []

This has the same check-before-insert rule, expected $O(n)$ time, and $O(n)$ auxiliary space. The difference is what the stored information can answer: seen tells you whether a value occurred; earlier_index also tells you where. Neither structure needs the input sorted.

The lookup pattern extends beyond sums. If you need two values whose absolute difference is a given nonnegative gap, the current value could pair with an earlier value - gap or an earlier value + gap. The state remains a set of earlier values; what changes is the lookup condition:

def pair_with_gap(nums, gap):
    if gap < 0:
        return []

    seen = set()

    for value in nums:
        if value - gap in seen:
            return [value - gap, value]
        if value + gap in seen:
            return [value + gap, value]
        seen.add(value)

    return []

For gap = 0, the code still requires two occurrences: the first value is not in seen when checked, while a later equal value finds it. This illustrates the more general design question: given the current item, which earlier value or values would make an answer? Once you can state that condition, you can often replace repeated scans with fast membership checks.

Key takeaways

For pair-finding in an unsorted sequence, calculate the value needed to complete a pair and look for it among earlier items. Use a set if existence is enough, or a dictionary if you must retrieve information such as an index. Check before inserting to prevent one element from matching itself. The usual trade-off is expected $O(n)$ time instead of $O(n^2)$, at the cost of $O(n)$ auxiliary space.

Next, you’ll solve problems where the array is sorted or where positions in a string provide useful order. In those cases, two pointers can sometimes find an answer without storing a searchable history.