Skip to content
BytePatterns

Two Sum

Hash Tables: lesson 2 of 5

Remember what you have seen and the pair finds itself.

Lesson 2 of 5 · 5 min

Two Sum

Step 1 of 8

Checking every pair is O(n²). Instead, walk once and remember what has gone past.

The Idea

Comparing every pair costs O(n²). Instead, walk the list once and ask a map of seen values one question: has the complement — target minus this value — already gone past? A hash lookup answers instantly, so a single pass settles it.

Real-World Example

A hardware shop keeps a bin of timber offcuts, and a customer needs exactly 240 cm from two pieces. The clerk measures each offcut once, jotting lengths on a pad, and after every measurement glances at the pad for the missing remainder instead of re-searching the bin.

The Code

def two_sum(nums, target):
    seen = {}                    # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:         # the partner already went past
            return (seen[need], i)
        seen[x] = i              # remember x for whoever needs it
    return None

print(two_sum([90, 40, 200, 150], 240))   # (1, 2)  -> 40 + 200
print(two_sum([5, 5], 10))                # (0, 1)

Your turn

Fill in the blank.

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

print(two_sum([90, 40, 200, 40], 240))   # want (1, 2)

Mini quiz

1 / 3

Time complexity of the hash-map two-sum?