• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Find common elements in 3 int array

 
Raj Kumar Bindal
Ranch Hand
Posts: 418
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And can you please explain a bit on the below requirement?
Raj Kumar Bindal wrote:with minimum time/space complexity.
 
Rob Spoor
Sheriff
Pie
Posts: 20546
56
Chrome Eclipse IDE Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hehe Rob... I din't know that.. thanks
 
Rob Spoor
Sheriff
Pie
Posts: 20546
56
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 10422
63
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 20546
56
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
True. Your example could have two possible outcomes, {2} or {2,2}. I assumed (bad, I know) that the result should be {2}.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic