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:

# find out the duplicates in the given list of objects and Big O

Ranch Hand
Posts: 541
Problem statement (AS IS): Write a program to find out the duplicates in the given list of objects. Explain the time complexity of your solution (Big O Notation)

Time complexity of getDuplicates method:

Let's assume that list has N elements.

- Collections.sort(input), O(N LogN)

O(N LogN) + O(1)
= O(N LogN)>

Saloon Keeper
Posts: 3336
46
I wouldn't use a sort(). A HashMap with count for a value would be quicker.

Saurabh Pillai
Ranch Hand
Posts: 541
Saurabh Pillai wrote:
Time complexity of getDuplicates method:

Let's assume that list has N elements.

- Collections.sort(input), O(N LogN)

O(N LogN) + O(1)
= O(N LogN)

Sorry I miscalculated this. It should be,

- Collections.sort(input), O(N LogN)
- for loop, O(N)

O(N LogN) + O(N) + O(1)
= O(N(LogN + 1))
= O(N LogN)

Saurabh Pillai
Ranch Hand
Posts: 541
Carey Brown wrote:I wouldn't use a sort(). A HashMap with count for a value would be quicker.

This is how I have implemented it.

Carey Brown
Saloon Keeper
Posts: 3336
46
Two tweaks I'd make to this. First, return List<String> instead of ArrayList<String>, always program to the interface if possible. And second, you are calling both contains() and get() when just calling get() and checking for null would suffice (and be more efficient).

Sheriff
Posts: 22846
43
You don't really need the Map with counts. The add(E) method of HashSet returns a boolean value which tells you whether you added a duplicate or not. All you need is something to count whichever boolean value means "duplicate".

But as for the OP: Yes, the sort is O(N log N), your evaluation of your code is correct. (Nothing in the question you posted asked you to find the most time-efficient implementation of the requirements.)

Carey Brown
Saloon Keeper
Posts: 3336
46
Paul Clapham wrote:You don't really need the Map with counts. The add(E) method of HashSet returns a boolean value which tells you whether you added a duplicate or not. All you need is something to count whichever boolean value means "duplicate".
If you return a Set<String> this would work, but if your return a List<String> then ["one","one","one"] would return a List with "one" in there twice. (unless I'm misunderstanding you)

Carey Brown
Saloon Keeper
Posts: 3336
46
Saurabh Pillai wrote:

In Java-8 this could be replaced with

Paul Clapham
Sheriff
Posts: 22846
43
I interpreted "find out the duplicates" to mean counting them. Possibly that was a careless reading of the question.

Sheriff
Posts: 21137
87
But you can still use it: