Find a common element within N arrays

Question

If I have N arrays, what is the best(Time complexity. Space is not important) way to find the common elements. You could just find 1 element and stop.

Edit: The elements are all Numbers.

Edit: These are unsorted. Please do not sort and scan.

This is not a homework problem. Somebody asked me this question a long time ago. He was using a hash to solve the problem and asked me if I had a better way.

Answer 1

The most direct method is to intersect the first 2 arrays and then intersecting this intersection with the remaining N-2 arrays.

If 'intersection' is not defined in the language in which you're working or you require a more specific answer (ie you need the answer to 'how do you do the intersection') then modify your question as such.

Without sorting there isn't an optimized way to do this based on the information given. (ie sorting and positioning all elements relatively to each other then iterating over the length of the arrays checking for defined elements in all the arrays at once)

Answer 2

I'd first start with the degenerate case, finding common elements between 2 arrays (more on this later). From there I'll have a collection of common values which I will use as an array itself and compare it against the next array. This check would be performed N-1 times or until the "carry" array of common elements drops to size 0.

One could speed this up, I'd imagine, by divide-and-conquer, splitting the N arrays into the end nodes of a tree. The next level up the tree is N/2 common element arrays, and so forth and so on until you have an array at the top that is either filled or not. In either case, you'd have your answer.

Without sorting and scanning the best operational speed you'll get for comparing 2 arrays for common elements is O(N²).

Answer 3

Create a hash index, with elements as keys, counts as values. Loop through all values and update the count in the index. Afterwards, run through the index and check which elements have count = N. Looking up an element in the index should be O(1), combined with looping through all M elements should be O(M).

If you want to keep order specific to a certain input array, loop over that array and test the element counts in the index in that order.

Some special cases:

if you know that the elements are (positive) integers with a maximum number that is not too high, you could just use a normal array as "hash" index to keep counts, where the number are just the array index.

I've assumed that in each array each number occurs only once. Adapting it for more occurrences should be easy (set the i-th bit in the count for the i-th array, or only update if the current element count == i-1).

EDIT when I answered the question, the question did not have the part of "a better way" than hashing in it.

Answer 4

The question asks is there a better way than hashing. There is no better way (i.e. better time complexity) than doing a hash as time to hash each element is typically constant. Empirical performance is also favorable particularly if the range of values is can be mapped one to one to an array maintaining counts. The time is then proportional to the number of elements across all the arrays. Sorting will not give better complexity, since this will still need to visit each element at least once, and then there is the log N for sorting each array.

Back to hashing, from a performance standpoint, you will get the best empirical performance by not processing each array fully, but processing only a block of elements from each array before proceeding onto the next array. This will take advantage of the CPU cache. It also results in fewer elements being hashed in favorable cases when common elements appear in the same regions of the array (e.g. common elements at the start of all arrays.) Worst case behaviour is no worse than hashing each array in full - merely that all elements are hashed.

Answer 5

function commonElement(array of n arrays input)
  head <- shift(input)
  for i <- 0..length(head)
    search <- head[i]
    for j <- 0..length(input)
      found <- false
      for k <- 0..length(input[j])
        if input[j][k] = search
          found <- true
      if found = false
        break
    if found = true
      return search
    else
      return failure

I think the above pseudocode should do what you need. It should run in O(nm^2) where n is the number of arrays and m is the length of the array.