# 5ms Java Using 1 hashset and time complexity of O(m+n)

• ``````HashSet<Integer> set = new HashSet<Integer>();
ArrayList<Integer> res = new ArrayList<Integer>();
//Add all elements to set from array 1
for(int i =0; i< nums1.length; i++) set.add(nums1[i]);
for(int j = 0; j < nums2.length; j++) {
// If present in array 2 then add to res and remove from set
if(set.contains(nums2[j])) {
set.remove(nums2[j]);
}
}
// Convert ArrayList to array
int[] arr = new int[res.size()];
for (int i= 0; i < res.size(); i++) arr[i] = res.get(i);
return arr;``````

• ok, but are you sure contains method is constant complexity ?

• Yes, set works similar to how map works, so it will hash the value and search in that particular index.
http://stackoverflow.com/questions/25247854/hashset-contains-performance

• @mitulshr oh yes that is right, I forgot it uses hash function .

• Why did you remove the element?

• We use remove function to avoid calculating twice when same numbers contained in the second array. For example, nums1 = [2,2], nums2 = [1,2,2,1]. Without remove function, "2" in nums2 will be counted twice. Since we only need one "2", we need set.remove().

• OMG I considered this problem more complicated because I think we need to consider the count of each arrays. I mean if nums1 has two '2', the nums2 must have exactly two '2' for intersection. So I used HashMap to store element and count by Key and values.

• Same idea, but shorter code,

``````    class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> numbers = new HashSet<>();
for (int n : nums1) { numbers.add(n); }
int[] res = new int[numbers.size()];
int cursor = 0;
for (int n : nums2) {
if (numbers.remove(n)) {
res[cursor++] = n;
}
}
return Arrays.copyOfRange(res,0,cursor);
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.