Thursday Code Puzzler: Intersection of Two Arrays

In Groovy, with Guava library

import com.google.common.collect.*;
def intersection(list1, list2) {
	Sets.intersection(Sets.newHashSet(list1), Sets.newHashSet(list2))
}
assert intersection([1,3,5,7,9],[1,2,3,4,5]) == [1,3,5] as Set

Python intersecting x and y (assuming no repetition):  set(x).intersection(y)

But if the arrays can have repeating members then sets can't be used.  ie:

For this to work I would use Counter:

from collections import Counter
def intersect(x,y):
    cx,cy = Counter(x), Counter(y)
    result = []
    for k in set(cx.keys()).intersection(cy.keys()):
        result.extend([k]*min(cx[k], cy[k]))
    return result

>>> intersect([1,1,1,2,2,2,2], [3,1,2,1,2])
[1, 1, 2, 2] 

Java

	public static Integer[] intersection(Integer[] arr1, Integer[] arr2) {
		List<Integer> result = new ArrayList<Integer>(Arrays.asList(arr1));
		result.retainAll(Arrays.asList(arr2));
		return result.toArray(new Integer[0]);
	}

Hi all, my solution is:  

public static List<Integer> getIntersection(int[] array1, int[] array2) {
     Set<Integer> inputs = new TreeSet<>();
     List<Integer> common = new ArrayList<>();
     
     for(int i=0;i<array1.length; i++){
       inputs.add(array1[i]);
     }
     
     for (int i=0;i<array2.length;i++){
         if (!inputs.add(array2[i]))
           common.add(array2[i]);
     }
     return common;
   }

int[] a = { 1, 3, 5, 7, 9 };int[] b = { 1, 2, 3, 4, 5 };List<Integer> aList = new ArrayList<Integer>();List<Integer> bList = new ArrayList<Integer>();for (int i : a) {aList.add(i);}for (int i : b) {bList.add(i);}aList.retainAll(bList);System.out.print(aList);

need to manual copy, Array.asList will not work

Ruby:

[1,3,5,7,9] & [1,2,3,4,5]

 Thanks Sam Fly.  Your solution works perfectly.

Intersection is defined on two sets, not on two arrays where duplicates are possible. That's why my solution "normalize" the Arrays.

The method has the side effect of sorting the arrays. This eliminates the need of copying the arrays and as a result the method needs less memory. I have not made any assumptions about the size of the arrays nor the possible difference in length. The resulting code contains some tweaks for special cases, like one array contains a million values while the other only contains a few or the arrays a disjunct.

It is moderate fast (slightly or up to 2-4 times faster then building Lists and use retainAll, depends on the data) and uses moderate memory. Have fun ;-)

    public static int[] intersection(int[] arr1, int[] arr2) {
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        int[] a1;
        int[] a2;
        int resLen;
        if (arr1.length >= arr2.length) {
            a1 = arr1;
            a2 = arr2;
            resLen = arr1.length;
        } else {
            a1 = arr2;
            a2 = arr1;
            resLen = arr2.length;
        }
        final int len1 = a1.length;
        final int len2 = a2.length;
        final int[] result = new int[resLen];
        int ridx = 0;
        int i = 0;
        int s = 0;
        while (i < len2) {
            int x = a2[i];
            if (x >= a1[s]) {
                final int pos = Arrays.binarySearch(a1, s, len1, x);
                if (pos >= 0) {
                    result[ridx] = x;
                    ridx++;
                    s = pos + 1;
                    while (s < len1 && a1[s] == x) {
                        s++;
                    }
                    if ( s >= len1) break;
                } else {
                    s = (pos * -1) - 1;
                    if (s >= len1) {
                        break;
                    }
                }
            } else {
                final int pos = Arrays.binarySearch(a2, a1[s]);
                if (pos >= 0) {
                    i = pos - 1;
                } else {
                    i = (pos * -1) - 2;
                }
            }
            ++i;
        }
        return Arrays.copyOf(result, ridx);
    }

Homepage 

These answers are all seriously lacking in algorithms. If you use a ready made set, then the problem has already been solved for you. For instance, the following ought to be fairly efficient in Scala, aside from boxing problems:

import scala.collecton.immutable.BitSet

BitSet(a1: _*) & BitSet(a2: _*)

The verbosity of some other languages hide the fact that there's no algorithm there, just the reuse of something someone else already wrote.

So I wrote this thing below, which is inspired by bucket sort. Instead of sorting, however, it simply recurses until there's only two numbers in the bucket. It will fail is either array has duplicates in itself, so I suppose it is only a partial solution to the problem.

The efficiency depends on how well bucket size is chosen, and how many duplicates there are, with large buckets being effective when input size and the number of duplicates is high and bad otherwise. The default works well (beats nlogn, though I left out the initial conversion of arrays into lists) across the board in my testing.

I've left a step counter print for those who want to experiment with it, but be advised the step counter itself double the number of steps due to how List#size works.

def intersection(a1: Array[Int], a2: Array[Int], bucketBits: Int = 4): List[Int] = {
    val maskSize = 1 << bucketBits
    val maskShift = bucketBits
    val mask = maskSize - 1
    var steps = 0
    var result: List[Int] = Nil
    def recurse(input: Seq[Int], mask: Int, shift: Int) {
      def index(n: Int) = (n & mask) >> shift
      if (mask == 0) result ::= input.head
      else {
        val buckets = Array.fill(maskSize)(List[Int]())
        input foreach { n => buckets(index(n)) ::= n }
        buckets foreach {
          case bucket @ (a :: b :: rest) => 
            if (rest.isEmpty) { if (a == b) result ::= a }
            else recurse(bucket, mask << maskShift, shift + maskShift)
          case _ =>
        }
        steps += input.size + buckets.size
      }
    }
    if (a1.nonEmpty || a2.nonEmpty) recurse(a1 ++ a2, mask, 0)
    println("Done in "+steps+" steps")
    result
}

// Given two unsorted slices of ints, find all of
// their common elements.
//
// The problem statement didn't specify whether the
// result should be sorted, so this implementation
// does not sort the intersection result.
func intersect(left, right []int) []int {
    // The map associates each element of a source
    // with a bitmap showing where it was found.
    found := make(map[int]int)
    mark(found, left, 1)
    mark(found, right, 2)
    // Once all sources are marked, keys whose
    // values have all bits on are in the intersection.
    result := make([]int, 0)
    for k, v := range found {
        if v == 3 {
            result = append(result, k)
        }
    }
    return result
}

func mark(m map[int]int, ns []int, bit int) {
    for _, v := range ns {
        m[v] |= bit
    }
}