Solvequill Blog · coding · 3 min read · 24 views

Two Sum: why one loop beats two, measured rather than asserted

Both solutions are correct. Only one stays usable at a million elements, and the reason is a single line of the inner loop.

Published: August 25, 2026

Loading the lesson…

The Solvequill lesson for this question.

The question

Given an array of integers and a target, return the indices of the two numbers that add to the target. Write both the nested-loop solution and the hash-map solution, and explain precisely why one is O( $n^{2}$ ) and the other O(n).

The bottom row is why this matters: half a trillion versus a million.

What to notice first

The nested loop re-asks a question it has already answered. For each element it scans everything after it, looking for a partner — but the array does not change, so the information needed was available the first time through. A hash map is what remembers it.

Working it through

The direct solution checks every pair. It is correct, and it is the one worth writing first:

Python

1def two_sum_nested(nums, target):2    for i in range(len(nums)):3        for j in range(i + 1, len(nums)):4            if nums[i] + nums[j] == target:5                return [i, j]6    return []

Count the work. The outer loop runs n times; the inner loop runs n-1 times, then n-2, and so on. That sum has a closed form:

(n - 1) + (n - 2) + \dots + 1 = \frac{n ( n - 1 )}{2}

The $\frac{n ^{2}}{2}$ term dominates, so this is $O (n^{2})$ — doubling the input roughly quadruples the work.

\frac{n ( n - 1 )}{2} \sim \frac{n ^{2}}{2} \Rightarrow O (n^{2})

The hash-map version asks a different question. Instead of 'is there a partner ahead of me?', it asks 'have I already seen my partner?' — and a dictionary answers that in constant time:

Python

1def two_sum_hash(nums, target):2    seen = {}3    for i, value in enumerate(nums):4        partner = target - value5        if partner in seen:6            return [seen[partner], i]7        seen[value] = i8    return []

One pass, and each step does a constant amount of work. The array is touched exactly once:

n \times O (1) = O (n)

The answer

O (n^{2}) ⟶ O (n)

The trade is memory for time: the dictionary holds up to n entries, so the space cost goes from O(1) to O(n). At a million elements that is a few tens of megabytes against roughly 5× $1 0^{11}$ comparisons — an easy trade, but a trade nonetheless.

The mistake this one catches

Prefer to watch it? The lesson above walks through every line.

Turn your own question into an explanation video

Type the question or upload a photo; Solvequill produces a narrated video that walks through the solution step by step.

Open Solvequill