Solving with dicts

Implement the count and group patterns in Python, then solve the classic two-sum problem with O(n) dict lookup.

Key-value thinking described two patterns. Now let's implement them in Python, then apply the same idea to a problem where it matters a great deal: two-sum.

The three functions

Read each function carefully before running. Predict the output, then run and check yourself.

Python — editable, runs in your browser

def count_words(text):
  # Count occurrences of each word in a string.
  # Single pass: one dict entry per unique word, incremented each time we see it.
  words = text.split()
  counts = {}
  for word in words:
      counts[word] = counts.get(word, 0) + 1
  return counts

def group_by_length(words):
  # Group words by their length.
  # Key insight: use len(word) as the dict key, append words to the list there.
  groups = {}
  for word in words:
      length = len(word)
      if length not in groups:
          groups[length] = []
      groups[length].append(word)
  return groups

def two_sum(nums, target):
  # Find two indices whose values sum to target. Return them as a tuple.
  # Naive approach: check every pair — O(n^2).
  # Dict approach: for each number x, check if (target - x) is already in seen.
  # If yes, we have our pair. If no, record x's index. One pass — O(n).
  seen = {}   # value -> index
  for i, x in enumerate(nums):
      complement = target - x
      if complement in seen:
          return (seen[complement], i)
      seen[x] = i
  return None

# --- count_words ---
sentence = "the cat sat on the mat the cat"
print("word counts:", count_words(sentence))

# --- group_by_length ---
words = ["cat", "dog", "elephant", "ant", "bee", "ox", "rhino"]
print("by length:", group_by_length(words))

# --- two_sum ---
nums = [2, 7, 11, 15]
print("two_sum([2, 7, 11, 15], 9):", two_sum(nums, 9))   # (0, 1)
print("two_sum([2, 7, 11, 15], 18):", two_sum(nums, 18)) # (1, 2)

Why the dict makes two-sum fast

The brute-force approach to two-sum is a pair of nested loops: for each element, scan the rest of the list looking for its complement. That is O(n²) — at n=10 000 it means roughly 100 million comparisons.

The dict approach does one pass. At each index i, the question is: "have I already seen target - nums[i]?" The seen dict answers that in O(1). So the whole function is O(n) — linear in the length of the list.

This is the general trade: spend O(n) space on a dict so that membership checks drop from O(n) to O(1). Whenever you catch yourself writing a loop that searches a list you've already processed, stop and ask whether a dict would remove the inner scan entirely.

dict.get(key, default) avoids a KeyError when the key is absent — it returns default instead. counts.get(word, 0) + 1 is the idiomatic way to increment a counter that may not exist yet.

Where to go next

Next: Big-O intuition — a precise vocabulary for talking about how fast (or slow) an algorithm grows as the input gets larger.

Finished reading? Mark it complete to track your progress.

The three functions

Why the dict makes two-sum fast

Where to go next

On this page