AI Hints
Home›DSA in Python Tutorial›Sets and Hashing Practice
DSA in Python · Lesson 23 of 132

Practice: Two Sum

The classic interview question.

⏱ 2 min read▶ Video at 26:27🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Given a list of numbers and a target, find the positions of two numbers that add up to the target. The list isn't sorted, so two pointers won't work directly. Pause and think. How could a dictionary help?

Practice: Two Sum
From the video: Practice: Two Sum
  • Two numbers that add to a target
  • The list isn't sorted
  • How could a dict help?

The slow way

The obvious answer tries every pair, with a loop inside a loop. It works, but it's O of N squared. With a hundred thousand numbers, that's billions of checks.

two_sum_slow.pypython
def two_sum_slow(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return i, j

print(two_sum_slow([2, 7, 11, 15], 9))
Output
(0, 1)

The fast way

For each number, we ask, what partner do I need? That's the target minus the number. A dictionary remembers every number we've seen, and where it was. If the partner is already in the dictionary, we're done. Otherwise, we store this number, and move on. Run it. One pass, so it's O of N.

two_sum.pypython
def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        need = target - n
        if need in seen:
            return seen[need], i
        seen[n] = i

print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 8, 4, 5], 9))
Output
(0, 1)
(2, 3)

Summary

Two sum asks, what partner do I need, and a dictionary remembers what we've seen. That turns O of N squared into O of N. It's a pattern you'll use again and again.

Key takeaways
  • need = target - n
  • Remember what you've seen
  • O(n) with a dict
Next up: Practice: First Unique — count, then search