Count order pairs summing to a target size

Question

You have a list of order sizes and a target notional T. Count how many unordered pairs of positions (i, j) with i < j satisfy sizes[i] + sizes[j] == T. Repeated sizes count as distinct positions.

sizes = [1, 1, 2, 3, 3], T = 4
-> 4            # each of the two 1s pairs with each of the two 3s

Return the number of such pairs. Aim for $O(n \log n)$ dominated by the sort.

Accepted Answer

Sort the sizes, then sweep a pointer in from each end. When the two ends sum below T, the left value is too small, so advance left; when they sum above, retreat right. When they sum to exactly T, count the block of equal values on each side and multiply, that counts every cross pair at once. If the two ends hold the same value, then everything between them is that value, and the pairs are "n choose 2". Tracing [1, 1, 2, 3, 3] with T = 4: the ends 1 and 3 match the target; there are two 1s and two 3s, giving 2 2 = 4 pairs. Time O(n \log n), space O(1) beyond the sort. The trickiest edge case i…

Count order pairs summing to a target size

Your answer

More Coding questions