Common Elements Of Three Arrays

March 17, 2015

If I had to write that program while standing in front of an interviewer writing on a whiteboard, I think I would take the simple approach: scan through the first two arrays, keeping common elements, then scan the result with the third array. Here’s the two-array version, using lists because that is simpler in Scheme:

(define (common2 xs ys)
  (let loop ((xs xs) (ys ys) (zs (list)))
    (cond ((or (null? xs) (null? ys))
            (reverse zs))
          ((< (car xs) (car ys))
            (loop (cdr xs) ys zs))
          ((< (car ys) (car xs))
            (loop xs (cdr ys) zs))
          (else (loop (cdr xs) (cdr ys)
                  (cons (car xs) zs))))))

I wrote that about as fast as I can type, and it worked the first time; it’s a standard recursion that every Scheme programmer internalizes quickly. Then it’s easy to extend to three lists:

(define (common3 xs ys zs)
  (common2 (common2 xs ys) zs))

And here’s the example problem:

> (define xs '(1 5 10 20 40 80))
> (define ys '(6 7 10 20 80 100))
> (define zs '(3 4 15 20 30 70 80 120))
> (common2 xs ys)
(10 20 80)
> (common2 ys zs)
(20 80)
> (common2 xs zs)
(20 80)
> (common2 (common2 xs ys) zs)
(20 80)
> (common3 xs ys zs)
(20 80)
> (common3 '(1 5 5 5) '(3 4 5 5 10) '(5 5 10 20))
(5 5)

As an added bonus, this approach generalizes to more than three inputs in an obvious way:

(define (common . xss)
  (fold-left common2 (car xss) (cdr xss)))

> (common xs ys zs)
(20 80)

This algorithm is reasonably efficient, running in time O(kn) where k is the number of lists and n is the length of the second-longest list. It’s also simple to code and hard to get wrong, and I could be confident writing it on a whiteboard while an interviewer watched. If you want to have some fun, look at the solutions at Career Cup and try to convince yourself that they are correct.

You can run the program at http://ideone.com/ER0ChF.

Advertisements

Pages: 1 2

12 Responses to “Common Elements Of Three Arrays”

  1. klettier said

    My solution is to find shortest two arrays to process biggest one only one time.
    This allows for searching for only common integers from the two shortest arrays in bigest one.

    void Main()
    {
    	var ar1 = new[]{1,5,10,20,40,80,999,999};
    	var ar2 = new[]{6,7,10,20,80,100,5,999,999};
    	var ar3 = new[]{3,4,15,20,30,70,80,120,999,999};
    	
    	var bigestAndShortestArrays = FindBigestAndShortestArrays(new int[][]{ar1,ar2,ar3});
    	
    	List<int> numberToFindInBigestArray = new List<int>();
    	
    	for(int a = 0; a < bigestAndShortestArrays.Item2[0].Length; a++)
    		for(int aa = 0; aa < bigestAndShortestArrays.Item2[1].Length; aa++)
    			if(bigestAndShortestArrays.Item2[0][a] == bigestAndShortestArrays.Item2[1][aa])
    				numberToFindInBigestArray.Add(bigestAndShortestArrays.Item2[0][a]);
    	
    	numberToFindInBigestArray = numberToFindInBigestArray.Distinct().ToList();
    	
    	List<int> numbersInAllArrays = new List<int>();
    	
    	for(int a = 0; a < bigestAndShortestArrays.Item1.Length; a++)
    		for(int aa = 0; aa < numberToFindInBigestArray.Count; aa++)
    			if(bigestAndShortestArrays.Item1[a] == numberToFindInBigestArray[aa])
    				numbersInAllArrays.Add(bigestAndShortestArrays.Item1[a]);
    	
    	numbersInAllArrays.Dump();
    }
    
    Tuple<int[], int[][]> FindBigestAndShortestArrays(int[][] arrs)
    {
    	if(arrs.Length != 3)
    	throw new InvalidOperationException("tabs must be an array of 3 arrays");
    
    	var shortests = new int[2][];
    	int[] biggest = null;
    	
    	if(arrs[0].Length <= arrs[1].Length)
    	{
    		if(arrs[1].Length <= arrs[2].Length)
    		{
    			shortests[0] = arrs[0];
    			
    			if(arrs[1].Length <= arrs[2].Length)
    			{
    				shortests[1] = arrs[1];
    				biggest = arrs[2];
    			}
    			else
    			{
    				shortests[1] = arrs[2];
    				biggest = arrs[1];
    			}
    		}
    		else
    		{
    			shortests[0] = arrs[1];
    			
    			if(arrs[0].Length <= arrs[2].Length)
    			{
    				shortests[1] = arrs[0];
    				biggest = arrs[2];
    			}
    			else
    			{
    				shortests[1] = arrs[2];
    				biggest = arrs[0];
    			}
    		}
    	}
    	
    	return Tuple.Create(biggest,shortests);
    }
    

    Output:

    20
    80
    999
    999

  2. Francesco said

    Haskell:

    f a b c                         | any null [a, b, c] = []
    f la@(a:as) lb@(b:bs) lc@(c:cs) | all (==a) [b, c]   = a : f as bs cs
                                    | otherwise          = f (d la) (d lb) (d lc)
        where d cs = if head cs == maximum [a,b,c] then cs else tail cs
    

    There is probably a more concise solution using lists comprehension, but alas it eludes me

  3. Scott said
    public class ThreeArrays {
    	
    	public static void main(String[] args){
    		System.out.println(commonNumbers(new Integer[]{1,5,10,20,40,80}, 
    				new Integer[]{6,7,10,20,80,100}, new Integer[]{3,4,15,20,30,70,80,120}));
    
    		System.out.println(commonNumbers(new Integer[]{1,5,5,5}, 
    				new Integer[]{3,4,5,5,10}, new Integer[]{5,5,10,20}));
    	}
    
    	public static List<Integer> commonNumbers(Integer[]... arrays){
    		
    		if(arrays.length < 2)
    			return null;
    		
    		List<Integer> common = new ArrayList<Integer>();
    		int[] matches = new int[arrays[0].length];
    
    		for(int i = 1; i < arrays.length; i++){
    			int x = 0, y = 0;
    
    			while(x < arrays[0].length && y < arrays[i].length){
    				if(arrays[0][x] < arrays[i][y]){
    					x++;
    				}
    				else if(arrays[0][x] > arrays[i][y]){
    					y++;
    				}
    				else{
    					matches[x++] += 1;
    					y++;
    				}
    			}
    		}
    
    		for(int i = 0; i < matches.length; i++){
    			if(matches[i] == arrays.length-1){
    				common.add(arrays[0][i]);
    			}
    		}
    		return common;
    	}
    }
    
  4. mcmillhj said

    Similar solution in SML:

    fun intersect (xs, ys) = let
    fun loop(out, _, []) = List.rev out
    | loop(out, [], _) = List.rev out
    | loop(out,left as x::xs, right as y::ys) =
    if x < y then loop(out, xs, right)
    else if y < x then loop(out, left, ys)
    else loop(x::out, xs, ys)
    in
    loop([], xs, ys)
    end

    fun nintersect [] = []
    | nintersect (xs::xss) = List.foldl intersect xs xss;
    [/sourcecode]

  5. mcmillhj said

    Sorry, issue with formatting:

    fun intersect (xs, ys) = let
        fun loop(out, _, [])      = List.rev out
          | loop(out, [], _)      = List.rev out
          | loop(out,left as x::xs, right as y::ys) =
               if x < y then loop(out, xs, right)
               else if y < x then loop(out, left, ys)
               else loop(x::out, xs, ys)
    in
        loop([], xs, ys)
    end
    
    fun nintersect []  = []
      | nintersect (xs::xss) = List.foldl intersect xs xss;
    
  6. matthew said

    This one is like Scott’s – for each element in the first array, discarding lower elements in the other arrays, moving on to the next element if no match is found. A nice flourish is to use a sentinel element at the end of each array, when a match is found and it’s the sentinel element we break the loop. No other bounds checking is needed:

    #include <stdio.h>
    #include <limits.h>
    int a[] = { 0,10,20,30,40,40,50,60,70,80,100,MAXINT };
    int b[] = { 5,20,20,40,40,80,MAXINT};
    int c[] = { 10,20,30,40,40,45,50,60,80,MAXINT};
    int main()
    {
      int ai = 0, bi = 0, ci = 0;
      for ( ; ; ai++) {
        while (b[bi] < a[ai]) bi++;
        if (b[bi] > a[ai]) continue;
        while (c[ci] < a[ai]) ci++;
        if (c[ci] > a[ai]) continue;
        if (a[ai] == MAXINT) break;
        printf("%d ", a[ai]);
        bi++; ci++;
      }
      printf("\n");
    }
    
  7. Paul said

    In Python. This works for an arbitrary number of arrays.

    def common_n(*arrays):
        """ make a sorted array with (value, iter) tuples
            as long as the first value is lower than the last:
                increase the first value and keep the array sorted
        """
        def common(*arrays):
            its = [iter(a) for a in arrays]
            while 1:
                vals = sorted([(next(it), it) for it in its])
                while vals[0][0] < vals[-1][0]:
                    v, it = vals.pop(0)
                    while v < vals[-1][0]:
                        v = next(it)
                    vals.append((v, it)) # now v >= last value in array, so we can append
                yield vals[0][0]
        return list(common(*arrays))
    
  8. Mike said

    The Python standard library collections.Counter acts like a multi-set, making this problem a one-liner.

    from collections import Counter
    from functools import reduce
    from operator import and_
    
    def find_common(*args):
    	return sorted(reduce(and_, map(Counter, args)).elements())
    
  9. Keval said

    for(p=0;p<a.length;p++)
    {
    for(q=0;q<b.length;q++)
    {
    if(b[q]==a[p])
    {
    // System.out.println("matching values found in array a and b:::"+b[q]);
    for(r=0;r<c.length;r++)
    {
    if(c[r]==b[q])
    {
    common[common_ite]=c[r];
    System.out.println("common integer found:::"+common[common_ite]);
    common_ite++;
    break;
    }
    //ends for loop r….for c array
    }
    break;
    //end if of b array…
    }

    //end for loop of q …for b array…
    }
    //ends main foor loop..of array a…
    }

  10. Keval said

    It can be made more efficient by using common array with length of shortest array…use of break is not encouraged…but its fast and in any interview..it maybe helpful in time constraint..

  11. matthew said

    OK, here’s another one, same trick with sentinels. Iterate down all 3 lists, if the current element in list i is less than the current element in list i+1 (mod 3), skip it. If no element is skipped, they must all be the same. Possibly does more comparisons than my other solution, but at least uses INT_MAX properly:

    #include <stdio.h>
    #include <limits.h>
    int a[] = { 0,10,20,30,40,40,50,60,70,80,100,INT_MAX };
    int b[] = { 5,20,20,40,40,80,INT_MAX };
    int c[] = { 10,20,30,40,40,45,50,60,80,INT_MAX };
    int main()
    {
      int ai = 0, bi = 0, ci = 0;
      while (true) {
        if (a[ai] < b[bi]) ai++;
        else if (b[bi] < c[ci]) bi++;
        else if (c[ci] < a[ai]) ci++;
        else if (a[ai] == INT_MAX) break;
        else {
          printf("%d ", a[ai]);
          ai++; bi++; ci++;
        }
      }
      printf("\n");
    }
    
  12. Rutger said

    Wrote my own Bag implementation in Python, for the heck of it. Although obviously I should have used collections.Counter :)

    class Bag():
        def __init__(self, l=None):
            self.data = {}
            if l:
                for e in l:
                    self.insert(e)
    
        def __str__(self):
            result = '_'*4+'bag'+ '_'*4 + '\n'
            for e in sorted(self.data.keys()):
                result += ("[%s%sx] %s\n"%(" "*(3-len(str(self.data[e]))), self.data[e], e))
            return result
            
        def insert(self, e):
            try:
                self.data[e] += 1
            except KeyError:
                self.data[e] = 1
    
        def remove(self, e):
            try:
                self.data[e] -= 1
            except KeyError:
                raise Exception("Bag.remove(): %s not found."%e)
    
        def get(self, e):
            try:
                return (e, self.data[e])
            except KeyError:
                return ()
    
        def clear(self):
            self.__init__()
    
        def union(self, bag):
            result = Bag()
            for e in self.data:
                result.data[e] = self.data[e]
                try:
                    result.data[e] += bag.get(e)[1]
                except:
                    result.data[e] = bag.get(e)[1]
            return result
    
        def intersection(self, bag):
            result = Bag()
            for e1 in self.data:
                try:
                    n = bag.get(e1)[1]
                    result.data[e1] = min(self.data[e1], n)
                except:
                    pass
            return result
    
        @staticmethod
        def test():
            b1 = Bag()
            for x in range(7):
                b1.insert(3)
            b1.insert(849401284)
            print b1
            print b1.get(3)
            b1.remove(3)
            try:
                b1.remove(4)
            except Exception, e:
                print e
            b1.insert("asdf'")
            print "-"*30, "Result", "-"*30
            print b1
            print "-"*30, "Union self", "-"*30
            b2 = b1.union(b1)
            print b2
            print "-"*30, "intersection self with union", "-"*30
            b3 = b1.intersection(b2)
            print b3
    
    
    # Bag.test()
    b1 = Bag([1,5,10,20,40,80])
    b2 = Bag([6,7,10,20,80,100])
    b3 = Bag([3,4,15,20,30,70,80,120])
    print b1.intersection(b2).intersection(b3)
    b1 = Bag([1,5,5,5])
    b2 = Bag([3,4,5,5,10])
    b3 = Bag([5,5,10,20])
    print b1.intersection(b2).intersection(b3)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: