1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Please see the description/hover of tag C++. $\endgroup$
    – greybeard
    Jun 9, 2021 at 21:20

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ 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. $\endgroup$
    – Pseudonym
    Jun 9, 2021 at 4:29
  • $\begingroup$ Is there anyway you can post the code for it please ? $\endgroup$
    – Gajab
    Jun 9, 2021 at 9:32
  • $\begingroup$ 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 $\endgroup$
    – Gajab
    Jun 9, 2021 at 10:38
  • $\begingroup$ Any help on the same? $\endgroup$
    – Gajab
    Jun 9, 2021 at 11:36
  • $\begingroup$ @Gajab I guess the explanation is pretty much sufficient. I do not know what to add more. $\endgroup$ Jun 9, 2021 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.