Two Sum

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)

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)