posted 1 month ago

Time complexity of

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)

=

**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)**>

Saurabh Pillai

Ranch Hand

Posts: 541

posted 1 month ago

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))

=

Saurabh Pillai wrote:

Time complexity ofgetDuplicatesmethod:

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

posted 1 month ago

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).

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

posted 1 month ago

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.)

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.)

posted 1 month ago
Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

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)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".

posted 1 month ago

But you can still use it:

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions