# Need help to explain why second approach(4ms) beat first one(8ms)

• First approach

• Initialize two sets to eliminate duplicate elements from nums1 and nums2, take O(n)
• Traverse setB in order to find element i in setA, takes O(length of setB)
• Save result for output
``````public int[] intersection4(int[] nums1, int[] nums2) {
if (nums1.length == 0 || nums2.length == 0) {
return new int[0];
}
Set<Integer> setA = new HashSet<>();
for (int i : nums1)
setA.add(i);

Set<Integer> setB = new HashSet<>();
for (int i : nums2)
setB.add(i);

int[] result = new int[nums1.length];
int index = 0;
for (int i : setB) {
if (setA.contains(i))
result[index++] = i;
}
return Arrays.copyOfRange(result, 0, index);
}
``````

Second approach

• Sort two arrays with O( nlgn )
• For binary search takes O( lgn)
``````public int[] intersection(int[] nums1, int[] nums2) {
if (nums1.length == 0 || nums2.length == 0) {
return new int[0];
}

Arrays.sort(nums1);
Arrays.sort(nums2);
int r[] = new int[Math.min(nums1.length, nums2.length)];
int c = 0;
for (int i : nums1) {
if (c == 0 || i != r[c - 1]) {
if (Arrays.binarySearch(nums2, i) >= 0) {
r[c++] = i;
}
}
}

return Arrays.copyOf(r, c);
}
``````

Thanks for your help in advance.

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