programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Finding the intersection and union in two sorted Lists

lewis manuel
Ranch Hand
Posts: 64
2
This is an assignment that I've been doing and the specifications for it are that I need to implement two methods(intersection and union) using the comparable interface(only allowed to use Java Collection API basic methods) and explain their complexity.

I've finished the first part(creating the intersection method) and described it's complexity.

The way I did it was by using a binary search on the second sort list while using a for loop for the first list so I can traverse through the first list and second list in one go. If I find a match in both sorted lists, then I add them to a list that contains all objects that are distinct and are the intersection of List 1 and List 2.

In essence, the time complexity for my method is nlogn. the n is for the for loop through the first list. The logn is because of the binary search. I don't know if it possible to make it a little bit better.

I notice that my previous code didn't check for duplicates. What I added is a variable previous that keeps track of the previous element that was found. Why I think this works is because we have a sorted list. We can have a sorted list that have duplicates like this {6, 6, 6} but not a list like this {4, 6, 4}. What this means is that the duplicate has to always be behind the element that was found previously given by the rule that we have a sorted list which or may not contain duplicates.

Piet Souris
Master Rancher
Posts: 2044
75
You could make it a little better, although I think it is still nlogn.
Suppose your lists are A and B, and that the first element of A
equals the nth element of B. Then for the second element of A,
you only need to look at B, starting from position n + 1 (or n,
depending how you handle duplicates).

lewis manuel
Ranch Hand
Posts: 64
2
I've changed the intersection to look like this

Suppose if we have these sorted lists

A = {1, 2, 6, 9, 9}
B = {1, 2, 9 12}

For these two lists I would have to do four binary searches instead of five. The previous code did 5 anyways even though there is no point because you have a duplicate.

 It is sorta covered in the JavaRanch Style Guide.