# Non-quadratic search for specific difference between elements in sorted array

New to computer science and am attempting to verify if there are any non-quadratic approaches (i.e. better performance than Big-O of n^2) for finding a potential specific difference between either adjacent or nonadjacent elements in a sorted array of integers?

For example, if you have an array that's already been sorted, like so:

[1, 4, 6, 6, 10, 12, 13, 15, 16]


And you want to find if there's a difference between any of these elements that equals 3, the pairs here would be 4, 1 and 15, 12 and 13, 10.

But is there an algorithmic approach that would allow me to find these pairs without using two for loops?

• I know of two. (1) Sort the numbers, then walk 2 pointers from opposite ends towards each other, moving the left pointer rightward whenever the sum of the pointed-to elements is too small, and the right pointer leftward whenever it is too large; the invariant here is that any satisfying pair must be taken from the interval of elements spanned by the 2 pointers. (2) Build a hash table containing every element as key (the value for each key is unimportant), then loop through every element $x$ again, checking whether $x+d$ or $x-d$ is in the hashtable. – j_random_hacker Oct 23 '17 at 17:05
• @j_random_hacker Why not write an answer? – Yuval Filmus Oct 23 '17 at 19:04

2. Build a hash table containing every element as key (the value for each key is unimportant), then loop through every element $x$ again, checking whether $x+d$ or $x−d$ is in the hashtable.
• Thank you for the two suggestions, much appreciated. Regarding method 1, how would we wind up with the pair 4, 1 in the array [1, 4, 6, 6, 10, 12, 13, 15, 16] ? – AdjunctProfessorFalcon Oct 23 '17 at 19:31
Since the array is sorted, you can use two pointers technique. Set both of them on first element $v_1$. First pointer called $i_1$ indicates smaller item, second pointer called $i_2$ indicates bigger one. When $v_{i_2} - v_{i_1}$ is bigger or equal than required difference, move pointer $i_1$ forward, otherwise move pointer $i_2$. Since each pointer traverses each item exactly once, this is effectively linear solution.