How to Find Common Elements of Two UnSorted Array? Below is a simple Java Code which shows it.
Steps:
- Find 1st small array.
- Iterate through small array and find elements in largest array.
- In case of match, add it to separate new array.
- Display final array.
Approach-1:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
package com.crunchify; import java.util.HashSet; /** * @author Crunchify.com */ public class CrunchifyIntersection { public static void main(String[] args) { Integer[ ] arrayOne = { 1, 4, 5, 2, 7, 3, 9 }; Integer[ ] arrayTwo = { 5, 2, 4, 9, 5 }; Integer[ ] common = CrunchifyIntersection.findCommon( arrayOne, arrayTwo ); System.out.print( "Common Elements Between Two Arrays: " ); for( Integer entry : common ) { System.out.print( entry + " " ); } } public static Integer[ ] findCommon( Integer[ ] arrayOne, Integer[ ] arrayTwo ) { Integer[ ] arrayToHash; Integer[ ] arrayToSearch; if( arrayOne.length < arrayTwo.length ) { arrayToHash = arrayOne; arrayToSearch = arrayTwo; } else { arrayToHash = arrayTwo; arrayToSearch = arrayOne; } HashSet<Integer> intersection = new HashSet<Integer>( ); HashSet<Integer> hashedArray = new HashSet<Integer>( ); for( Integer entry : arrayToHash ) { hashedArray.add( entry ); } for( Integer entry : arrayToSearch ) { if( hashedArray.contains( entry ) ) { intersection.add( entry ); } } return intersection.toArray( new Integer[ 0 ] ); } } |
Output:
|
1 |
Common Elements Between Two Arrays: 2 4 5 9 |
Approach-2
Below approach is suggested by our reader Maksudur rahman as you see it in below comment section. Please find here complete example.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
package crunchify.com.tutorials; import java.util.Arrays; import java.util.LinkedHashSet; import java.util.Set; /** * @author Crunchify.com * */ public class CrunchifyIntersection { public static void main(String[] args) { Integer[] arrayOne = { 1, 4, 5, 2, 7, 3, 9 }; Integer[] arrayTwo = { 5, 2, 4, 9, 5 }; Set<Integer> crunchifySet1 = new LinkedHashSet<Integer>(Arrays.asList(arrayOne)); Set<Integer> crunchifySet2 = new LinkedHashSet<Integer>(Arrays.asList(arrayTwo)); for (Integer crunchify : crunchifySet2) { if (!crunchifySet1.add(crunchify)) { System.out.println("The duplicate element of an Array is " + crunchify); } } } } |
Output:
|
1 2 3 4 |
The duplicate element of an Array is 5 The duplicate element of an Array is 2 The duplicate element of an Array is 4 The duplicate element of an Array is 9 |
what will be the complexity in approach2??
since iterating one hashet and simutaneoulsy trying to add in 2nd set.So it will be
o(n) only
since i read add() in set in o(1)
Agree. Big-O time complexity if the code inside loop is taking constant time to execute, i.e. if its time complexity is O(1), then the complexity of the loop will be O(1*n) = O(n).
What about this solution:
Set mySet = new LinkedHashSet(Arrays.asList(array1));
Set mySet1 = new LinkedHashSet(Arrays.asList(array2));
for(Integer i : mySet1){
if (!mySet.add(i)){
System.out.println(“The duplicate element of an Array is ” +i);
}
}
Hi Maksudur – thanks for code block. It worked perfectly fine. I’ve just updated tutorial with your code base and mentioned your reference.
why you need so complex answer when O(n2) is complexity. simply use 2 for loops
Hi Sumit – can you please explain your query in details? We do have 2 for loops in solution already.
Would be nice if you could share code sample here.