What is a good way to find pairs of numbers, each stored in a different array, such that the difference between the first and second number is 1?

Question

Suppose you have several arrays of integers. What is a good way to find pairs of integers, not both from the same list, such that the difference between the first and second integer is 1?

Naturally I could write a naive algorithm that just looks through each other list until it finds such a number or hits one bigger. Is there a more elegant solution?

I only mention the condition that the difference be 1 because I'm guessing there might be some use to that knowledge to speed up the computation. I imagine that if the condition for a 'hit' were something else, the algorithm would work just the same.

Some background: I'm engaged in a bit of research mathematics and I seek to find examples of a certain construction. Any help would be much appreciated.

Answer 1

This sounds like a good candidate for the classic merge sort where the final stage is not a unification but comparison.

And the magnitude of the difference wouldn't affect this, but thanks for adding the information.

Answer 2

Even though you state the second list is in an array, if you could put it in a hashmap of some sort then you could make it faster than just the naive approach.

Basically, Loop through the first array. Look to see if there exists an object in the hashmap that is one larger than the current array value.

That way you can build up pairs of numbers that meet your requirements.

I don't know if it would be as flexible as you would like though.

Basically, you may want to consider other data structures, to help you find a better solution.

Answer 3

I'd start by sorting each array. Preferably with an algorithm that runs in O( n log(n) ) time.

When you've got a bunch of sorted arrays, you can set a pointer to the start of each array, check for any +/- 1 differences in the values of the pointers, and increment the value of the smallest-valued pointer, repeating until you've reached the max length of all but one of the arrays.

To further optimize, you could keep the pointers-values in a sorted linked list, and build the check function into an insertion sort. For each increment, you could remove the previous value from the list, and step through the list checking for +/- 1 comparison until you get to a term that is larger than a possible match. That way, if you're searching a bazillion arrays, you needn't check all bazillion pointer-values - you only need to check until you find a value that is too big, and ignore all larger values.

---

If you've got any more information about the arrays (such as the range of the terms or number of arrays), I can see how you could take advantage of that to make much faster algorithms for this through clever uses of array properties.

Answer 4

You have o(n log n) from the sorting.

You can also the the search in o(log n) for each element, if you have some dynamic queryset. You can sort the arrays and then for each element in the first array binary search his upper_bound and lower_bound in the second array and check the difference.