Given an array of numbers and a target, return the positions of two numbers that add up to the target. The direct method tries every pair. A hash map remembers each value it has passed, so every number asks one question: has my complement already gone by?
Two nested loops. The outer loop fixes i, the inner loop tries every j to its right. Each cell in the matrix below is one pair (i, j), so the work is the number of cells that light up before the first hit.
How to read this: Each square is one pair: row i with column j. The number in it is a[i] + a[j]; the search stops at the first square that equals the target. The small number under each array value is its index (position).
Try this: Pick late hit and watch how many squares light up before the gold one.
Each unordered pair appears once in the upper triangle. The diagonal is skipped because a position can't pair with itself, and the lower triangle would repeat the upper one. That leaves n(n−1)/2 cells, so doubling the array roughly quadruples the worst case.
Walk left to right once. For each x, compute the complement need = target − x and look it up in a map of values already seen. If it's there, you're done. If not, store x → i and move on. The map below is a real chained hash table: a key goes to bucket key mod m, and keys that share a bucket line up in a chain.
How to read this: Each row is a bucket, numbered on the left. A number goes in the row equal to its remainder after dividing by m (that is what "mod" means). Each chip shows a stored number and its position i.
Try this: Drag Buckets m to 1 and press Run: every number piles into one long row.
When the scan reaches index i, the map holds every earlier value. If some j < i completes the pair, the lookup at i finds it, so one pass is enough. Looking up before storing keeps a number from pairing with itself, yet [3, 3] with target 6 still works because the first 3 is already stored.
The bucket rule is plain remainder arithmetic, the same idea as in 003 · Number theory. With enough buckets the chains stay short and a lookup costs about the same at any size. Drag m to 1 and every key shares one chain: the map turns into a list, and the key comparisons grow like n² instead of n.
Run all three methods on the same random array of size N. Every value is distinct and even, and in "one pair" mode a single entry is made odd so exactly one pair hits the target. The counts are real: the page runs each algorithm and counts its work. Below the chart, the two-pointer method runs step by step on a sorted copy.
How to read this: Higher means more work. Each line is one method; the gold dashed line marks the N set by the slider, and the rings on it are the values in the readouts.
Try this: Switch to Linear: the red line shoots up while the green one stays flat.
How to read this: The top row is the array sorted from small to large; "#" shows where each value sat originally. L and R close in from both ends.
If p[L] + p[R] is too small, p[L] can't work with anything left, since p[R] is already the largest partner available. Drop it. If the sum is too big, p[R] is out for the same reason. Each step removes one value, so the scan takes at most n − 1 steps after the sort.
| Method | Time | Extra space |
|---|---|---|
| Every pair | O(n²) | O(1) |
| Hash map | O(n) expected | O(n) |
| Sort + two pointers | O(n log n) | O(1) values only |
Sorting scrambles the positions, so on its own the two-pointer scan returns two values. To answer with indices, sort (value, index) pairs as above, which costs O(n) extra space. The O(1) figure holds only when you may sort in place and only need the values.
The hash map's O(n) is an average. If every key landed in one bucket, as with m = 1 in Lab 2, it would fall back to quadratic work.