Count the pairs that fill a block

Question

Resting child orders have sizes (some can be negative, representing sells). You want to know how many pairs of them combine to exactly the block size.

sizes = [1, 5, 7, -1, 5], target = 6
-> 3          # (1,5), (1,5) using the other 5, and (7,-1)

Return the number of unordered index pairs $(i, j)$ with $i < j$ and sizes[i] + sizes[j] == target. Aim for $O(n)$ .

Accepted Answer

Walk once, keeping a map from value to how many times it has appeared so far. For each x, every earlier copy of target - x forms a valid pair, so add that count to the answer, then record x. Counting complements before inserting x avoids pairing an element with itself and never double-counts, because each pair is credited once, at its later element. Tracing [1, 5, 7, -1, 5], target 6: at 1 no 5 yet (0); at 5 one 1 seen (+1, total 1); at 7 no -1 (still 1); at -1 one 7 seen (+1, total 2); at 5 one 1 seen (+1, total 3). Answer 3, matching (1,5), (1,5), and (7,-1). Time O(n), space O(n). The coun…

Count the pairs that fill a block

Your answer

More Coding questions