Two solutions, one problem

Two solutions, one problem

In Data Structures you learned what lists, dictionaries, and sets are, and you met Big-O notation for describing how work grows with input size. This course is about algorithms, the step-by-step procedures for solving problems.

The interview game is almost never can you code, it is can you pick the faster procedure.

Here is the question this lesson uses throughout. Does any pair of numbers in a list add up to a target?

There are two honest ways to solve it.

1. Check every pair with a nested loop.
2. Walk the list once, remembering what has been seen in a set, and ask whether target - n has already appeared.

Both are correct, and correctness is where most people stop. They are not equally fast, and the difference can be measured rather than guessed at, which is what the next block does.

Counting the steps of both

Each function solves the same problem and counts its own work as it goes.

def pair_slow(nums, target):
    steps = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            steps += 1
            if nums[i] + nums[j] == target:
                return True, steps
    return False, steps

def pair_fast(nums, target):
    steps = 0
    seen = set()
    for n in nums:
        steps += 1
        if target - n in seen:
            return True, steps
        seen.add(n)
    return False, steps

nums = list(range(100))
print(pair_slow(nums, 197))
print(pair_fast(nums, 197))

Output

(True, 4950)
(True, 100)

The list holds 0 through 99, and both functions found an answer, so the difference is entirely in the cost of finding it.

pair_slow has the inner loop start at i + 1, which is what stops it from checking a pair twice or pairing a number with itself.

pair_fast has no inner loop at all. The if target - n in seen line asks a question a set can answer immediately, which is what replaces the scan.

The ordering inside pair_fast matters. Testing before seen.add(n) prevents a number from being paired with itself, which is the same discipline the two-sum solution used in Data Structures.

Reading the numbers

The target 197 is reachable only as 98 + 99, which is the very last pair the nested loop tries. That makes this the worst case for pair_slow and a fair look at what it costs.

So pair_slow did 4,950 steps, which is every pair of 100 items at 100 × 99 / 2, while pair_fast did 100 steps, one per item.

That is the practical meaning of the Big-O from Data Structures.

At n = 100 the gap is 4,950 against 100. At n = 100,000 it is about five billion against 100,000, which is the difference between an instant answer and a program that appears to hang.

The technique is worth keeping. Counting steps on small inputs is how you check a Big-O guess against reality, and it costs one counter variable.

Where the speed actually comes from

pair_fast wins because it visits each number once and asks the set a constant-time question. The speed comes from the algorithm rather than from the language.

Each number is touched exactly once, and the set answers whether target - n has been seen in O(1) on average, which is the hash-table behavior from Data Structures. One pass with O(1) work per item is O(n) in total.

Three explanations sound plausible here and are all wrong, so they are worth ruling out.

Sets do not store numbers in sorted order. A set is a hash table with no order to skip ahead through, and its speed comes from hashing straight to a bucket.

Python does not optimize single loops and penalize nested ones. Both loops run at the same speed per step, and pair_slow is slower because it takes about n²/2 steps, not because its steps are slower.

Neither function skips numbers larger than the target. That would be wrong anyway, since negative numbers mean a large value can still be half of a valid pair.

The general shape is worth naming, because it recurs for the rest of this course. An inner loop that only asks does this exist can almost always be replaced by a hash lookup.

The same trade on a different question

Now the question is whether the list contains a duplicate at all.

def dup_slow(nums):
    steps = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            steps += 1
            if nums[i] == nums[j]:
                return True, steps
    return False, steps

def dup_fast(nums):
    steps = 0
    seen = set()
    for n in nums:
        steps += 1
        if n in seen:
            return True, steps
        seen.add(n)
    return False, steps

nums = list(range(50)) + [25]
print(dup_slow(nums))
print(dup_fast(nums))

Output

(True, 975)
(True, 51)

dup_fast is the same shape as pair_fast: one loop, one set, and the membership test placed before the add. Testing after the add would find every value already present and report a duplicate on the first item.

The input is list(range(50)) + [25], so the only duplicate is 25, and dup_fast finds it on step 51 the moment it reaches the appended copy.

dup_slow needs 975 steps to reach the same conclusion, because the pair of 25s sits far into the nested scan.

The pattern to carry away is the substitution itself. Both problems asked have I seen something, and in both cases a set answered in O(1) what a loop was answering in O(n).

The gap at n = 1,000

For a list of 1,000 items, the nested loop's worst case is every pair, which is the number of ways to choose 2 items out of 1,000.

n · (n − 1) / 2 = 1000 · 999 / 2 = 499,500 steps

The one-pass set solution does at most 1,000 steps on the same list. That is a 500× gap on an input most people would call small, and it is why an interviewer asks you to beat the nested loop.

The ratio itself grows with n, because n²/2 divided by n is n/2. At a thousand items the fast version is about 500 times better, and at a million items about 500,000 times better.

That growing ratio is the real point. A constant-factor speedup keeps its advantage, while a better growth family widens its lead every time the input does.