I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Intersection of Two Arrays

01.31.2013
| 6350 views |
  • submit to reddit

Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Do you have code puzzlers that you'd like to share with the DZone community?  If so, please submit here. 

Find The Intersection of Two Arrays

Given two unsorted arrays as input to a function, find what the intersection (i.e. common elements) of these two arrays is. For example, with the arrays {1,3,5,7,9} and {1,2,3,4,5} the result would be {1,3,5}.

For this solution, focus on the efficiency.


Catch up on all our previous puzzlers here.

Comments

Vijay Nathani replied on Thu, 2013/01/31 - 8:28am

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

Adeel Shahzad replied on Thu, 2013/01/31 - 9:30am

This code is written in Java.=====================================================private static Integer[] getIntersection(int[] a, int[] b) {


List<Integer> intersectioned = new ArrayList<Integer>();


HashSet<Integer> intSet = new HashSet<Integer>();


int loopLimit = (a.length > b.length ? a.length : b.length);


for(int i = 0; i < loopLimit; i++) {


int setSizeBefore = intSet.size();


if(a.length > i)

intSet.add(a[i]);


int setSizeAfter = intSet.size();


if(setSizeBefore == setSizeAfter) {


if(a.length > i)

intersectioned.add(a[i]);


} setSizeBefore = intSet.size();


if(b.length > i)

intSet.add(b[i]);


setSizeAfter = intSet.size();


if(setSizeBefore == setSizeAfter) {


if(b.length > i)

intersectioned.add(b[i]);


}


}


return intersectioned.toArray(new Integer[intersectioned.size()]);


}

==========================================================

Iftah Haimovitch replied on Thu, 2013/01/31 - 8:56am

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] 



ebenezer raj replied on Thu, 2013/01/31 - 1:17pm


using q:

{x inter y}[(1 3 5 7 9);(1 2 3 4 5)] prints (1 3 5)

Sam Fly replied on Thu, 2013/01/31 - 4:37pm

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]);
	}

Alain Sahli replied on Thu, 2013/01/31 - 4:47pm

Scala:

def intersection(arr1: Array[Int], arr2: Array[Int]) = arr1.intersect(arr2)

Artur Kuban replied on Thu, 2013/01/31 - 5:03pm

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;
   }

Dmitri Bichko replied on Fri, 2013/02/01 - 2:04am

 Depends on the data.  If the int values are relatively small, a bit set intersection is by far the fastest (at least in Java):

   benchmark    us linear runtime
BinarySearch 275.1 =========
      ZigZag 368.8 ============
     HashSet 153.7 =====
     TreeSet 913.7 ==============================
       Trove 106.5 ===
      BitSet  21.1 =

vm: java
trial: 0
maxInt: 10000
sizeOne: 2500
sizeTwo: 5000

(and as usual, TreeSet is completely useless)

Jagdish Patel replied on Fri, 2013/02/01 - 4:36am

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);

Jagdish Patel replied on Fri, 2013/02/01 - 4:39am in response to: Sam Fly

Will not work on Array.asList, as it return fix size list, will get unsupportedoperationexception on retainAll.


Jagdish Patel replied on Fri, 2013/02/01 - 4:42am in response to: Jagdish Patel

need to manual copy, Array.asList will not work

Sam Fly replied on Mon, 2013/02/04 - 2:29am in response to: Jagdish Patel

Perhaps you should read my solution more closely :)

Mark Thomas replied on Wed, 2013/02/06 - 8:54am

Ruby:

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

Debmalya Jash replied on Wed, 2013/02/06 - 9:18am

Hi Sam Fly,

I like your solution.


Mark Harris replied on Wed, 2013/02/06 - 11:18am

 Thanks Sam Fly.  Your solution works perfectly.

Aaron Sawyer replied on Wed, 2013/02/06 - 4:43pm

I'm tired of fighting this site's unfriendly code formatting. Javascript solution is in my public PasteBin : http://pastebin.com/TFzw7W1t

...and here is a simple HTML page to test it with, also on PasteBin: http://pastebin.com/N48dg4VN

Stefan Roeper replied on Thu, 2013/02/07 - 1:50pm

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 

Vladi Vainer replied on Sat, 2013/02/09 - 6:36am in response to: Sam Fly

here is the same idea, but with generics

    public static <T> Set<T> intersect(Collection<T> left, Collection<T> right) {
        //check for null
        left.retainAll(right);        
        return new HashSet<T>(left);
    }

Daniel Sobral replied on Tue, 2013/02/12 - 5:30pm

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
}

Joel Neely replied on Sun, 2013/03/10 - 7:03am

Here's a solution using Go. // 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 key (from any source) // with a bitmap showing its sources. found := make(map[int]int) mark(found, left, 1) mark(found, right, 2) result := make([]int, 0)         // Once all sources are marked, the keys whose         // values have all bits on are in the intersection.  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 } }

Joel Neely replied on Sun, 2013/03/10 - 7:13am

Here's a solution using Go.
// 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
    }
}
(I hope the code survives my struggles with this site's embedded editor.)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.