• Post Reply Bookmark Topic Watch Topic
  • New Topic

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

 
Ranch Hand
Posts: 541
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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)
- duplicates.add(a);, for HashSet add is constant O(1)

O(N LogN) + O(1)
= O(N LogN)>
 
Saloon Keeper
Posts: 3336
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I wouldn't use a sort(). A HashMap with count for a value would be quicker.
 
Saurabh Pillai
Ranch Hand
Posts: 541
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Saurabh Pillai wrote:
Time complexity of getDuplicates method:

Let's assume that list has N elements.

- Collections.sort(input), O(N LogN)
- duplicates.add(a);, for HashSet add is constant O(1)

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)
-- duplicates.add(a);, for HashSet add is constant O(1)

O(N LogN) + O(N) + O(1)
= O(N(LogN + 1))
= O(N LogN)
 
Saurabh Pillai
Ranch Hand
Posts: 541
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.



Time Complexity: about O(N)
 
Carey Brown
Saloon Keeper
Posts: 3336
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Saurabh Pillai wrote:

In Java-8 this could be replaced with

 
Paul Clapham
Sheriff
Posts: 22846
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I interpreted "find out the duplicates" to mean counting them. Possibly that was a careless reading of the question.
 
Sheriff
Posts: 21137
87
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But you can still use it:
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!