Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Find common elements in 3 int array

Raj Kumar Bindal
Ranch Hand
Posts: 418
• 1
Hi,

i have 3 int arrays. I need to find common elements in those arrays with minimum time/space complexity. Please let me know how can we do this with best performance.

example: if contents of three arrays are {2,4,5,79} {54,6,4,2} {45,4,2,98}, then the output should be {2,4}

John Jai
Rancher
Posts: 1776
Add the array elements into a Map<Integer,Integer> where the key denotes the actual number and the value is a counter. Then on iterating the map checks whether its value is greater than 2 (found in all three arrays).

Utility method to add into a Map. You should call this method will all the three arrays.

You can also use this method to find the counter of numbers in an array for your other question in the thread - http://www.coderanch.com/t/563884/java/java/Finding-top-repeated-numbers-array.

John Jai
Rancher
Posts: 1776
And can you please explain a bit on the below requirement?
Raj Kumar Bindal wrote:with minimum time/space complexity.

Rob Spoor
Sheriff
Posts: 20527
54
• 1
It can be done a lot easier, using Set and retainAll. Create one set with the contents of the first array, then use retainAll to keep elements that are also in the other arrays.

John Jai
Rancher
Posts: 1776
hehe Rob... I din't know that.. thanks

Rob Spoor
Sheriff
Posts: 20527
54
You're welcome.

Raj Kumar Bindal, keep in mind that performance is dependent on the selected collections. I suggested Set because then you can use HashSet or LinkedHashSet with constant-time lookup. That way you will need to loop only through one of the Sets when calling retainAll. If you would use List then you would need to loop through both, worsening performance from O(n) (single loop + constant lookup) to O(m*n) (nested loop).

Winston Gutkowski
Bartender
Posts: 10417
63
• 1
Rob Spoor wrote:It can be done a lot easier, using Set and retainAll. Create one set with the contents of the first array, then use retainAll to keep elements that are also in the other arrays.

Totally agree, but it does depend on Raj's requirements if the arrays can contain duplicate values. If they can't, then Set is definitely the way to go (in fact, the arrays themselves should probably be Sets). If duplicates are allowed, then Raj needs to tell us what what he would expect from something like:
{2,4,5,2,13,2,79} {54,2,6,4,2} {45,2,42,98,2,2}

Winston

Rob Spoor
Sheriff
Posts: 20527
54
True. Your example could have two possible outcomes, {2} or {2,2}. I assumed (bad, I know) that the result should be {2}.