Take the 2-minute tour ×

I have few arrays of integers. Elements in each array are ordered. Arrays does not have duplicates.

I need to join all arrays into one so the resulting array contains only elements which exist in every array.

For example, I have arrays

(1,2,3,4,5) (2,3,5) (1,2,4,5)

The result has to be (2,5)

What is the best way to do it to achieve best performance?

share|improve this question
Might your arrays have duplicates? –  Don Roby Oct 2 '12 at 22:15
No, arrays does not have duplicates –  Artyom Krivokrisenko Oct 2 '12 at 22:39
the arrays count is dynamic? –  Elbek Oct 2 '12 at 22:59
yes, it is dynamic. But I can assume than it usually will be less then 10. –  Artyom Krivokrisenko Oct 2 '12 at 23:28
add comment

3 Answers

up vote 8 down vote accepted

If the arrays are expected to contain many different numbers and only few present in all of them,

  • pick the two smallest arrays, compute their intersection by stepping through them sequentially (like for a mergesort), O(len1 + len2)
  • while not all arrays have been scanned, pick the next smallest array, and compute its intersection with the intersection of the previously handled arrays, using a sequential scan if length(intersection)*log(length(array)) >= length(array), and looking up the elements of the intersection in array otherwise.

Worst case complexity is O(sum(lengths)), if you're lucky, you get around k * sum(log(length)), where k is the number of elements in the intersection.

share|improve this answer
add comment

This should work:

  • Create one index for each array
  • if for each array the element at the respective index is the same, add the element to your result list and increase each index by one
  • otherwise increase the index pointing to the lowest element
  • repeat until the first array is exceeded

This should also work if the arrays can contain more than one instance of a number, e.g. arrays (1,1,2,2), (2,2,3,3) would result in (2,2).

share|improve this answer
add comment

This is what my thinking: create one HashMap<Integer, Integer> it will be like numer->hits ; iterate over all array:

  • if element exist in hashMap then increment count(value), ie count++;
  • if element not exist then write count = 1 to value

After all you will have, number->count


So you again iterate over HashMap and print if(value==arrays.lenth)

So Space is O(N) and O(N) steps.

note hashmap's access is constant time(yahoooooo).

share|improve this answer
add comment

Your Answer


