Find unique common element from 3 arrays

Question

Original Problem:
I have 3 boxes each containing 200 coins, given that there is only one person who has made calls from all of the three boxes and thus there is one coin in each box which has same fingerprints and rest of all coins have different fingerprints. You have to find the coin which contains same fingerprint from all of the 3 boxes. So that we can find the fingerprint of the person who has made call from all of the 3 boxes.

Converted problem:
You have 3 arrays containing 200 integers each. Given that there is one and only one common element in these 3 arrays. Find the common element.
Please consider solving this for other than trivial O(1) space and O(n^3) time.

Answer 1

If you sort all the arrays first O(n log n) then it will be pretty easy to find the common element in less than O(n^3) time. You can for example use binary search after sorting them.

Answer 2

Use a hash table for each integer and encode the entries such that you know which array it's coming from - then check for the slot which has entries from all 3 arrays. O(n)

Answer 3

Some improvement in Pelkonen's answer:
From converted problem in OP:

"Given that there is one and only one common element in these 3 arrays."

We need to sort only 2 arrays and find common element.

Answer 4

O(N) solution: use a hash table. H[i] = list of all integers in the three arrays that map to i.

For all H[i] > 1 check if three of its values are the same. If yes, you have your solution. You can do this check with the naive solution even, it should still be very fast, or you can sort those H[i] and then it becomes trivial.

If your numbers are relatively small, you can use H[i] = k if i appears k times in the three arrays, then the solution is the i for which H[i] = 3. If your numbers are huge, use a hash table though.

You can extend this to work even if you can have elements that can be common to only two arrays and also if you can have elements repeating elements in one of the arrays. It just becomes a bit more complicated, but you should be able to figure it out on your own.

Answer 5

Use a hashtable mapping objects to frequency counts. Iterate through all three lists, incrementing occurrence counts in the hashtable, until you encounter one with an occurrence count of 3. This is O(n), since no sorting is required. Example in Python:

def find_duplicates(*lists):
  num_lists = len(lists)
  counts = {}
  for l in lists:
    for i in l:
      counts[i] = counts.get(i, 0) + 1
      if counts[i] == num_lists:
        return i

Or an equivalent, using sets:

def find_duplicates(*lists):
  intersection = set(lists[0])
  for l in lists[1:]:
    intersection = intersection.intersect(set(l))
  return intersection.pop()

Answer 6

If you want the fastest* answer:

• Sort one array--time is N log N.
• For each element in the second array, search the first. If you find it, add 1 to a companion array; otherwise add 0--time is N log N, using N space.
• For each non-zero count, copy the corresponding entry into the temporary array, compacting it so it's still sorted--time is N.
• For each element in the third array, search the temporary array; when you find a hit, stop. Time is less than N log N.

Here's code in Scala that illustrates this:

import java.util.Arrays

val a = Array(1,5,2,3,14,1,7)
val b = Array(3,9,14,4,2,2,4)
val c = Array(1,9,11,6,8,3,1)

Arrays.sort(a)
val count = new Array[Int](a.length)
for (i <- 0 until b.length) {
  val j =Arrays.binarySearch(a,b(i))
  if (j >= 0) count(j) += 1
}
var n = 0
for (i <- 0 until count.length) if (count(i)>0) { count(n) = a(i); n+= 1 }
for (i <- 0 until c.length) {
  if (Arrays.binarySearch(count,0,n,c(i))>=0) println(c(i))
}

With slightly more complexity, you can either use no extra space at the cost of being even more destructive of your original arrays, or you can avoid touching your original arrays at all at the cost of another N space.

---

Edit: * as the comments have pointed out, hash tables are faster for non-perverse inputs. This is "fastest worst case". The worst case may not be so unlikely unless you use a really good hashing algorithm, which may well eat up more time than your sort. For example, if you multiply all your values by 2^16, the trivial hashing (i.e. just use the bitmasked integer as an index) will collide every time on lists shorter than 64k....

Answer 7

Let N = 200, k = 3,

1. Create a hash table H with capacity ≥ Nk.

2. For each element X in array 1, set H[X] to 1.

3. For each element Y in array 2, if Y is in H and H[Y] == 1, set H[Y] = 2.

4. For each element Z in array 3, if Z is in H and H[Z] == 2, return Z.

5. throw new InvalidDataGivenByInterviewerException();

O(Nk) time, O(Nk) space complexity.