educative.io

Union/Intersection issues

Courses
,
#1

I believe the given Union solution breaks when one list is empty and the other has duplicates. The given union requirement is stated as:
" Given two lists, A and B , the union is the list that contains elements or objects that belong to either A or to B or to both but duplicates are not allowed."
So in that case the result will have duplicates.

Another issue is that it is not clear whether we should create a new list with new pointers or just reuse the pointers from the given list. Solution given is with the latter, but both seems to be reasonable and the question should have made it clear.

One last thing: the Intersection time complexity is vagally explained. I didn’t understand the max/min part. Please elaborate.

Type your question above this line.

Course: https://www.educative.io/collection/5642554087309312/5646276079124480
Lesson: https://www.educative.io/collection/page/5642554087309312/5646276079124480/5187211452481536

#2

Hi @Jorge_Amengol
It did not break. Instead, it prints the second list as it is, but yes, it will print duplicate values. Thank you for pointing out the issue. It will be fixed soon.
Secondly, the time complexity of intersection is max(O(mn), O(min(m,n)^2)) because the outer loop will run m times. The inner loop will run n times, so its time complexity will be 0(mn), and we are also using the removeDuplicates() function, whose time complexity is O(min(m,n)^2). So the overall complexity will be the maximum of both complexities, i.e., max(O(mn), O(min(m,n)^2))

#3

Hi Rabia,
I didn’t mean it would crash, I meant that it would break the defined invariant as I pointed out.
Thanks for elaborating on the complexity.