Does a pair of sizes differ by exactly d

Question

Given a list of order sizes and a non-negative difference d, decide whether some two of them differ by exactly d, that is, whether there exist positions i and j with sizes[j] - sizes[i] == d.

sizes = [1, 5, 3, 8], d = 2
-> True            # 3 and 5 differ by 2 (also 1 and 3)

Return True if such a pair exists, else False. Aim for $O(n \log n)$ .

Accepted Answer

Sort the sizes and run two pointers i and j. Widen the gap by advancing j when the current difference is too small, and narrow it by advancing i when it is too large. Because the array is sorted, this sweep visits every achievable difference in monotone order. Keep j strictly ahead of i so an element is never paired with itself (unless d is zero and duplicates exist). Tracing [1, 5, 3, 8] with d = 2: sorted it is [1, 3, 5, 8]. The pair 1 and 3 differs by exactly 2, so the answer is True. Time O(n \log n) from the sort, space O(1) beyond it. The guard if i == j: j += 1 keeps the two pointers f…

Does a pair of sizes differ by exactly d

Your answer

More Coding questions