Interview question: find common element in 3 arrays

[cool dude]

This is an algorithm question asked at an interview.

You have 3 arrays and for simplicity we'll say they're equal length and SORTED.
Example:

a1 = {2, 4, 7, 9}
a2 = {4, 5, 6, 11}
a3 = {1, 3, 4, 7}

The task is to find the number of common elements between all 3 arrays. So in this example the output will be 1 since there is only one common element in all 3 arrays which is 4.

Obviously you can solve this using 3 for loops and iterate through each array. You can even solve with 2 for loops while iterating through the first array and the inner for loop iterates through the other 2 arrays... However, this is highly inefficient as this has time complexity of O(n^3) and O(n^2) respectively.

Does anyone know of any good algorithms for solving this problem?

My only efficient algorithm I came up with as follows:
1. Iterate through each element in the array
2. Create Hashtable
3. check if the element is already in the Hashtable
3.1 If it is then increment the value of that element
3.1.1 If that value is 3 then increment our local count since we found a common element in all 3 arrays
3.2 if the element is not in the Hashtable then add it to the Hashtable
4. print count

However, this requires the use of a Hashtable meaning we increase our data space. Is there a better or easier way of doing this?

[Zren]

Your current idea is flawed.

Eg:
a1 = {}
a2 = {1}
a3 = {1, 1}

[cool dude]

Zren @ Wed Jul 11, 2012 6:04 pm wrote:

Your current idea is flawed.

Eg:
a1 = {}
a2 = {1}
a3 = {1, 1}

Your example is flawed as I said all 3 arrays must be same length. Also the elements in each array are unique so you won't have a3 = {1,1}

[Dreadnought]

My first instinct would be to keep track of 3 indices, one for each array and a total of course.
Starting with the first value in each array, do the following

Check if all 3 values are equal, if so increment the total and all indices by 1.
Otherwise, increment the index of lowest value by 1.
Repeat until you reach the end of one list (at this point you are done)

This would use a single loop and at first glance seems reasonably efficient since each iteration guarantees that you advance in one of the lists. This means you have at most 3*n iterations of your loop.

[chrisbrown]

I think this works, generalized to N arrays:

code:

Keep N indexes, one for each array, all initialized to the beginning of their respective arrays. Keep a counter commonCount initilaized to 0 Iterate over the first array only. For each element e {         initialize a counter matchCount to 1         for each other array {                 increment the respective index until the indexed element is not less than e                 if the value is equal to e, incremement matchCount         }         if matchCount is equal to N, increment commonCount }

After reaching the end of the first array, commonCount contains the number of elements common to all arrays.

Indexes increase monotonically so the running time is O(L*N) for N arrays of length L.

Edit: Ha, three minutes too late.

[cool dude]

Wow way simpler than I thought. I guess thinking under pressure is a bit different.

Thanks a lot Dreadnought here is the code I wrote using the algorithm you explained:

code:

public class commonNumber {         public static void main (String[] args)         {                 int[] arr1 = {2, 4, 7, 9};                 int[] arr2 = {4, 5, 6, 11};                 int[] arr3 = {1, 3, 4, 7};                                 int cnt1 = 0, cnt2 = 0, cnt3 = 0;                 int common = 0;                                 while (cnt1 < arr1.length && cnt2 < arr2.length && cnt3 < arr3.length)                 {                         if (arr1[cnt1] == arr2[cnt2] && arr1[cnt1] == arr3[cnt3])                         {                                 common++;                                 cnt1++;                                 cnt2++;                                 cnt3++;                         }                         else                         {                                 int min = Math.min(arr1[cnt1], arr2[cnt2]);                                 min = Math.min(min, arr3[cnt3]);                                 if (min == arr1[cnt1])                                         cnt1 = cnt1+1;                                 else if (min == arr2[cnt2])                                         cnt2 = cnt2 + 1;                                 else                                         cnt3 = cnt3 + 1;                         }                 }                                 System.out.println(common);         } }

[wtd]

code:

let in_list x lst =    let rec f' x lst a =       match lst with            [] -> a          | (y::ys) when a -> a          | (y::ys) -> f' x ys (x = y)    in       f' x lst false            let rec all f lst =    match lst with         [] -> true       | (x::xs) when not (f x) -> false       | (x::xs) -> all f xs            let rec which f lst lst_lst =    match lst with         [] -> None       | (x::xs) ->            if all (fun y -> f x y) lst_lst then               Some x            else               which f xs lst_lst                            let solution lst lst_lst =    which in_list lst lst_lst;;

[Raknarg]

I had a thought. If they're aleady sorted, could you just mergesort them together and then use a single for loop to find three arrays elements that are the same in order?

[wtd]

I implemented Tony's algorithm as per our discussion of this, which scales to any size dataset, but requires that all arrays be sorted. Arrays are never mutated, so there's a minimal, linearly scaling memory hit. The program also never scrubs over any array element twice.

code:

open Printf open Array module A = Array let solution arr_arr =         let rec starting_indices = A.make (A.length arr_arr) 0         and len = A.length arr_arr         and all_starts_equal () =                 let first = arr_arr.(0).(starting_indices.(0))                 and i = ref 1                 and break = ref false                 and result = ref true                 in                         (                                 while !i < len && not !break do                                         if first <> arr_arr.(!i).(starting_indices.(!i)) then (                                                 break := true;                                                 result := false);                                         i := !i + 1                                 done;                                 !result                         )         and find_index start f arr =                 let i = ref start                 and index = ref 0                 and found = ref false                 in                         (                                 while !i < A.length arr && not !found do                                         if f arr.(!i) then                                                 (                                                         index := !i;                                                         found := true                                                 );                                         i := !i + 1                                 done;                                 !index                         )         and remove_all_less () =                 let rec first = arr_arr.(0).(starting_indices.(0))                 and i = ref 1                 and f x = x >= first                 in                         while !i < len do                                 let index = find_index starting_indices.(!i) f arr_arr.(!i) in                                         starting_indices.(!i) <- index;                                 i := !i + 1                         done         in                 (                         while not (all_starts_equal ()) do                                 starting_indices.(0) <- starting_indices.(0) + 1;                                 remove_all_less ()                         done;                         arr_arr.(0).(starting_indices.(0))                 )                 let data =         [|                 [| 2; 4; 7; 9 |];                 [| 4; 5; 6; 11 |];                 [| 1; 3; 4; 7 |]         |];;         Printf.printf "The common element is: %d\n" (solution data)

[Amarylis]

code:

e = 0 for i in li:     if (i in l2) & (i in l3):         e += 1 print (e)

Go go python power!

[Tony]

Amarylis @ Thu Jul 12, 2012 12:51 pm wrote:

Go go python power!

Great. What's the runtime complexity of looking up an element by value in array?

[wtd]

If you're going to use Python, at least make use of sets.

code:

data = [[2, 4, 7, 9 ], [4, 5, 6, 11], [1, 3, 4, 7]] print reduce(lambda x, y: set(x) & set(y), data)

Edit: I'm too tired to do the math, but shouldn't this scale reasonably well? The intersection gets simpler with each iteration of reduce, and we're not looping over each array more than once.

[Amarylis]

Tony @ Thu Jul 12, 2012 3:43 pm wrote:

Amarylis @ Thu Jul 12, 2012 12:51 pm wrote:

Go go python power!

Great. What's the runtime complexity of looking up an element by value in array?

O(N), which in three arrays would be O(N^3), I know, I was just trying to give the simple answer Sorry.


(I might be completely wrong on my Big-O notation)

[Brightguy]

Raknarg @ Thu Jul 12, 2012 10:44 am wrote:

I had a thought. If they're aleady sorted, could you just mergesort them together and then use a single for loop to find three arrays elements that are the same in order?

Yes indeed! Nice thought.

Amarylis @ Fri Jul 13, 2012 12:14 am wrote:

O(N), which in three arrays would be O(N^3), I know, I was just trying to give the simple answer Sorry.

As mentioned, since the third loop isn't nested it would only be O(n^2).

wtd @ Thu Jul 12, 2012 7:30 pm wrote:

Edit: I'm too tired to do the math, but shouldn't this scale reasonably well? The intersection gets simpler with each iteration of reduce, and we're not looping over each array more than once.

Python uses hash tables to implement sets, so in the worst case (maximum number of collisions) intersection will be O(n^2). It should perform better in practice, though.

[Raknarg]

@Bightguy I really don't know how the math works at all, but I'm assuming it would change the complexity from O(n^3) to O(n)*3.

I really should look this stuff up...