Find two orders with a given size difference

Question

You have an unsorted list of order sizes and a positive threshold d. You want two orders whose sizes differ by exactly d.

sizes = [1, 5, 3, 4, 2], d = 3
-> (0, 3)          # sizes[3] - sizes[0] == 4 - 1 == 3

Return the indices of any two distinct entries whose difference is d, or None. Aim for $O(n)$ .

Accepted Answer

A pair differs by d exactly when the current value x has a partner equal to x - d or x + d seen earlier. Keep a hash map from value to index and check both complements before inserting x. Tracing [1, 5, 3, 4, 2], d = 3: after 1, 5, 3 the map is {1:0, 5:1, 3:2}. At x = 4 the complement 4 - 3 = 1 is present at index 0, so return (0, 3) (values 1 and 4, difference 3). Time O(n), space O(n). Checking both x - d and x + d guarantees you catch the pair from whichever side you reach second, without scanning the whole map. Takeaway. Difference is just sum with the target moved to the other side: the …

Find two orders with a given size difference

Your answer

More Coding questions