The Seen-So-Far Pattern

The pattern, abstractly

You're walking through an array (or string, or stream). For each element, the answer requires comparing it to something earlier in the sequence. The naïve approach is a nested loop. O(n²). The seen-so-far reframe is: maintain a hash map of relevant facts about everything you've seen so far, then at each new element ask a single O(1) question against that map.

The "relevant fact" varies by problem. Sometimes it's the value itself; sometimes the index of the value; sometimes the running prefix sum; sometimes the most recent index where a character appeared. The skeleton stays constant.

Instance 1. Two Sum (values)

"Given an array and a target, find two indices that sum to the target." The hash map stores value → index; at each element x, we look up target − x.

def two_sum(nums, target):
    seen = {}                                # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []

Query before recording, so an element can't pair with itself when target = 2x.

Instance 2. Subarray sum equals K (prefix sums)

"Count subarrays that sum to K." The relevant fact is the running prefix sum; at each step we ask "how many earlier prefixes had value running − k?" Same pattern, applied to derived values rather than the originals.

from collections import defaultdict

def subarray_sum(nums, k):
    seen = defaultdict(int)
    seen[0] = 1                              # the empty prefix
    running = count = 0
    for x in nums:
        running += x
        count += seen[running - k]
        seen[running] += 1
    return count

The seed seen[0] = 1 represents the empty prefix; without it, subarrays starting at index 0 are missed. See the prefix-sums deep-dive for the derivation.

Instance 3. Longest substring without repeating (last-seen index)

"Find the longest substring with no repeated characters." The relevant fact is "where did we last see this character?", the hash map maps character to most recent index. When we encounter a repeat that's still inside the current window, jump the window's left edge past it.

def longest_unique(s):
    last = {}                                # char -> last index seen
    l = best = 0
    for r, c in enumerate(s):
        if c in last and last[c] >= l:
            l = last[c] + 1                  # window jumps past the repeat
        last[c] = r
        best = max(best, r - l + 1)
    return best

Notice the structural similarity: walk forward, look something up keyed on the current element, update the map. The "answer" is now a window length rather than a pair, but the engine is the same.

Instance 4. Contains duplicate within K (presence + recency)

"Does any value appear twice within K positions of itself?" Map value to most recent index; on each new occurrence, check whether the previous occurrence is within K.

def contains_nearby_duplicate(nums, k):
    last = {}
    for i, x in enumerate(nums):
        if x in last and i - last[x] <= k:
            return True
        last[x] = i
    return False

Instance 5. Longest consecutive sequence (set membership)

"Given an unsorted array, find the length of the longest consecutive integer sequence." The relevant fact is "is this number present at all?", a set. The trick is to start streaks only from numbers with no predecessor.

def longest_consecutive(nums):
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 in s:
            continue                         # not a streak start
        length = 1
        while x + length in s:
            length += 1
        best = max(best, length)
    return best

This deserves a sentence on the amortised analysis. The total work across all "streak start" loops is O(n), each number is touched at most twice (once when checked, once when extending a streak it belongs to). The skip on x − 1 in s ensures non-start numbers contribute O(1) each. Total: O(n).

When the pattern doesn't apply

• The relation needs more than one prior element. "Find three indices that sum to target" needs a three-way relation; one hash-map lookup can't capture it. Sort + two-pointer (O(n²)) is the right shape, with the hash map at the inner level.
• The relation depends on element ordering, not just value. "Find the next greater element to the right" requires a stack, not a hash map.
• The hash map's keys explode. If the relevant facts are pairs, triples, or strings, the map's memory grows. Signature-based grouping (see Group Anagrams) handles this when the equivalence is well-defined; otherwise, prefer a different structure.

Universal implementation rules

1. Choose the right "relevant fact". Value, index, prefix sum, last-seen position, character count, pick the smallest piece of state that answers the question.
2. Query before record. Always. This prevents self-pairing on inputs like target = 2x.
3. Seed the empty case if needed. The empty prefix in subarray-sum problems; the empty window in sliding-window problems.
4. Use the right collection. Hash map when you need a value (index, count, position). Hash set when you only need membership. Counter when you need frequencies.

Complexity, reasoned

Each element is processed in O(1) amortised time, one hash-map lookup, one update. Total: O(n) time, O(n) space. The hash map's worst case is O(n) per operation under adversarial keys, but production runtimes use randomised hashing to prevent this. The pattern is one of the rare cases where the asymptotic is tight in both time and space and there's no further optimisation available.

Where beginners go wrong

• Recording before querying. Causes self-pairing bugs. The correct order is universal: look up the complement, then store yourself.
• Forgetting the empty-prefix seed in prefix-sum variants. Silently undercounts subarrays starting at index 0.
• Using a list when you need O(1) lookups. if x in big_list is O(n); inside a loop that's O(n²), back to brute force.
• Trying to use the pattern when the brute force is better. For tiny n (≤ 50), a nested loop with constant-factor wins might outperform a hash map. The pattern earns its keep when n grows past a thousand or so.

What to read next

Prefix Sums in Practice shows the pattern applied to derived values. Two Pointers & Sliding Window covers a different shape that handles "windows must remain valid" problems. The Hash Maps module ties the pattern back to the underlying data structure.