# Find non common numbers in two arrays

Given two arrays of integers, please write a function that returns all elements present in one of the two arrays but not both. E.g. f([ 1, 3, 5 ], [ 1, 2, 4, 5 ]) -> [ 2, 3, 4 ]

I know I can do this with two for loops that is O(n^2) but is there any better way ? Please help

• Please see the description/hover of tag C++. Jun 9, 2021 at 21:20

One simple solution is to merge the two arrays, sort them, and then remove the duplicate elements that belong to different arrays. It takes $$O(n \log n)$$ time.

Implementation:

1. For every element $$e$$ in array $$1$$, make a pair $$(e,1)$$. Let the array of these pairs be $$P_{1}$$. For every element $$e$$ in array $$2$$, make a pair $$(e,2)$$. Let the array of these pairs be $$P_{2}$$.
2. Merge $$P_{1}$$ and $$P_{2}$$. Let the merged array be $$P_{m}$$.
3. Sort $$P_{m}$$ in ascending order on the basis of the first value of a pair. If there is a tie then use the second value for comparison. You can employ merge sort since it takes $$O(n \log n)$$ time.
4. Keep only one copy of a pair that appears multiple times in the array. It takes $$O(n)$$ time.
5. Traverse the array from left to right. If any two consecutive pairs in the array have the same first value, remove them from the array.

The resulting array gives the required solution.

• This is an excellent solution. The only refinement I would add is that if the arrays are of very different lengths, then it may be worth sorting the shorter one, then traversing the longer one and using binary search to see if each element is present. Jun 9, 2021 at 4:29
• Is there anyway you can post the code for it please ? Jun 9, 2021 at 9:32
• And also it is not just removing duplicates, it’s about removing common elements. In the above example 1and 5 are common in both arrays so they are completely eliminated from resultant array Jun 9, 2021 at 10:38
• Any help on the same? Jun 9, 2021 at 11:36
• @Gajab I guess the explanation is pretty much sufficient. I do not know what to add more. Jun 9, 2021 at 11:51