Two-sum on a list of trade sizes

Question

You're given an unsorted list of trade sizes and a target block size. Two of your resting child orders should combine to fill the block exactly.

sizes = [2, 7, 11, 15], target = 9
-> (0, 1)          # sizes[0] + sizes[1] == 9

sizes = [3, 3], target = 6
-> (0, 1)

Return the indices of any two distinct entries that sum to the target, or None if no pair exists. Aim for $O(n)$ .

Accepted Answer

For each element x, the pair exists exactly when some earlier element equals 	ext{target} - x. Keep a hash map from value to index as you scan; before inserting the current element, check whether its complement is already in the map. This turns "search all previous elements" into an O(1) lookup. Tracing the first example: after seeing 2 the map is {2: 0}; at 7 the complement 9 - 7 = 2 is present, so we return (0, 1). Time O(n), space O(n). If the array were sorted you could instead run two pointers from both ends in O(n) time and O(1) space, but sorting first costs O(n \log n) and scrambles …

Two-sum on a list of trade sizes

Your answer

More Coding questions