2
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – j_random_hacker Oct 23 '17 at 17:05
  • 1
    $\begingroup$ @j_random_hacker Why not write an answer? $\endgroup$ – Yuval Filmus Oct 23 '17 at 19:04
3
$\begingroup$

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 difference 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.
$\endgroup$
  • $\begingroup$ 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] ? $\endgroup$ – AdjunctProfessorFalcon Oct 23 '17 at 19:31
  • $\begingroup$ You're welcome. I just realised that (1) gives an algorithm for finding a pair that sum to a given value -- I've now edited, sorry for the confusion. In your example, each of the differences 16-1, 15-1, 13-1, ..., 6-1 are too large, causing the pointer that started at the right-hand end to move left each time, until it stops at the 4, giving the difference 4-1 = 3. $\endgroup$ – j_random_hacker Oct 23 '17 at 20:25
  • $\begingroup$ thanks again. Just so I’m clear, in order to find all pairs with a difference of 3 using this method, you’d have to keep iterating over the array so it’s Big-O of n^2 right? $\endgroup$ – AdjunctProfessorFalcon Oct 23 '17 at 20:36
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.