Not the exercise, but the tool it needs. This finds the first word that appears twice, in one pass, by asking a dict "have I seen this before?" instead of searching the list again.
words = ["red", "blue", "green", "blue", "red"]
seen = {} # word -> the position it first appeared
for position, word in enumerate(words):
if word in seen: # instant, however long the list is
print(word, "first at", seen[word], "again at", position)
break
seen[word] = position
# -> blue first at 1 again at 3
- The question you keep asking
The nested-loop version asks "is there a match anywhere else in the list?" once for every item, and each time it searches from scratch. A dict answers that question in one step, so the work drops from every pair to every item.
- Check before you store
The loop looks the word up first and only then records it. Swap those two lines and every word "matches" itself, which in this exercise means using one number twice.
- What you store decides which match you get
Storing a position only the first time keeps the earliest one. Overwriting it every time keeps the latest. Both are one line; only one of them does what the contract asks.
For each number, you already know exactly which other number you need: target minus this one. The only question is whether you have seen it yet.
Keep a dict from number to the position you first saw it. For each new number, look up target - number in the dict before you add the number itself.
Loop with enumerate. If the complement is in the dict, return (dict value, current position). Otherwise record the current number, but only if it is not already there, so the earliest position survives. After the loop, return None.
def two_sum(nums, target): seen = {} for j, number in enumerate(nums): if target - number in ____: return (seen[____], j) if number not in seen: seen[number] = ____ return None
def two_sum(nums, target):
seen = {} # number -> first position it appeared at
for j, number in enumerate(nums):
wanted = target - number
if wanted in seen:
return (seen[wanted], j)
if number not in seen:
seen[number] = j
return None
When position j is checked, the dict holds only positions before j, so a number can never be paired with itself. Record first and look up second, and [3, 2, 4] with target 6 returns (0, 0).
It keeps the first position of every value, which is what makes the earliest partner win when a value repeats. Without it the dict quietly remembers the latest one instead, and nothing crashes to tell you.
The nested loop compares every pair, so doubling the list makes it four times slower. This version looks at each number once, so doubling the list doubles the time. Saying that out loud, and naming the dict as the reason, is most of the answer.
If the list is already sorted, you do not need the dict at all: one pointer at each end, moving inwards, finds a pair in one pass with no extra memory. And if you only need to know whether a pair exists, a set of numbers seen so far is enough. The dict is only there because the question asks for positions.
- Return every pair that adds up to target, each pair once, and decide what 'once' means when a value appears three times.
- Solve the sorted-list version with two pointers, then explain why sorting an unsorted list first loses the original positions.
- Three numbers that add up to target: what is the fastest you can do, and which part of this solution do you reuse?