78. Find a Pair With a Given Difference

Given an unsorted array of n integers and a positive value d, print 'Yes' if there exist two elements in the array whose absolute difference is exactly d, otherwise print 'No'.

Input: The first line contains an integer n. The second line contains n space-separated integers. The third line contains the positive integer d. Output: Print 'Yes' if two elements exist whose absolute difference is exactly d, otherwise print 'No'.

1 <= n <= 10^5, 1 <= d <= 10^9

Since the problem asks for absolute difference and d is given as positive, you only need to check x + d (not x - d) for every x, as long as you scan every element - the pair (a, b) where b - a = d will be found when you're looking at a and check for a + d = b.

You have a list of numbers and a target difference. You need to find out if any two numbers in the list are EXACTLY that far apart - like checking if any two people in a room have ages that differ by precisely 10 years. Brute force: Compare every pair of elements directly (two nested loops), checking if their absolute difference equals d - this costs O(n²), which is slow for large arrays. Optimised: Put every element into a hash set first, giving O(1) average lookup time. Then for each element x, just ask the set 'do you contain x + d?' instead of comparing x against every other element one by one - this collapses the pair-search from O(n) per element down to O(1) per element.

Sort the array first, then use two pointers i and j both starting at the beginning, repeatedly comparing a[j] - a[i]: if it equals d, report 'Yes'; if it is less than d, advance j to increase the gap; if it is greater than d, advance i to shrink the gap, being careful to keep i < j and skip past duplicate starting values. Because sorting brings equal-difference candidates near each other, both pointers only ever move forward, giving a single linear pass after the sort. Time: O(n log n) Space: O(1)

Compare every pair of elements (i, j) with i != j in the array and check whether the absolute difference between them equals d, printing 'Yes' as soon as such a pair is found. If no pair among all combinations satisfies the condition, print 'No'. This checks every possible pair directly. Time: O(n^2) Space: O(1)

Insert array elements into a hash set while scanning left to right, and for each new element x, check whether x + d or x - d has already been seen in the set; if so, a valid pair exists and 'Yes' can be printed immediately. If the entire array is scanned without ever finding such a companion value, print 'No'. Hash set lookups are expected O(1), so this avoids the need to sort altogether. Time: O(n) Space: O(n)

1. Put every number from the array into a hash set for instant lookup. 2. Go through each number in the array one at a time. 3. For the current number x, check whether (x + d) also exists in the set. 4. If it does, you've found your pair - answer Yes; if you finish scanning with no match, answer No.

Time: One pass to build the set, one pass to check each element - both linear, so the whole solution runs in time proportional to the array's size, not its square. Space: O(n), for storing every element in the hash set.

n = 1 (no pair possible, answer No), duplicate elements in the array, and n up to 10^5 with d up to 10^9 for performance and overflow-safe difference checks.

This is nearly identical in structure to the classic Two Sum problem, just checking for a DIFFERENCE instead of a SUM - recognizing that 'hash set + complement lookup' pattern instantly, regardless of the exact arithmetic relationship being tested, is a strong interview signal.