Method that remove duplicates from a list of words in Java Today, I took a coding challenge with this question:

Given a List of Strings, write a method removeDuplicates that removes duplicate words from the List and returns an ArrayList of all the unique words. The returned ArrayList should be lexically alphabetically.

One thing that I learned while doing this problem is a TreeSet. From my understanding it works like a set but adds elements in order.

From the code, I concluded that my time complexity would be O(n).
Can anyone offer suggestions or corrections?

public static ArrayList&lt;String&gt; removeDuplicates(List&lt;String&gt; input) {

    ArrayList&lt;String&gt; array = new ArrayList&lt;String&gt;();
    Set&lt;String&gt; noDups = new TreeSet&lt;String&gt;();

    if(input.isEmpty()){
        return array;
    }

    if(input.size() == 1){
        array.add(input.get(0));
        return array;
    }

    for(int i = 0; i &lt; input.size(); i++){
            noDups.add(input.get(i));
    }

    return new ArrayList&lt;String&gt;(noDups);
}
General advice

Prefer to declare variables by interfaces and not implementations. You don't need to specify that you use and return an ArrayList, specifying List is enough. So the first lines would be:

public static List&lt;String&gt; removeDuplicates(List&lt;String&gt; input) {
    List&lt;String&gt; array = new ArrayList&lt;String&gt;();
    Set&lt;String&gt; noDups = new TreeSet&lt;String&gt;();


Complexity

Javadoc for TreeSet says:


  This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).


Since you are performing a log(n) operation \$n\$ times, this becomes n * log(n).

Unnecessary edge cases

This is your main code:

for(int i = 0; i &lt; input.size(); i++){
        noDups.add(input.get(i));
}


Now let's take a look at your special cases:

if(input.isEmpty()){
    return array;
}


We can see that this would be handled correctly by your main code.

Your other special case:

if(input.size() == 1){
    array.add(input.get(0));
    return array;
}


This too would be handled correctly by your main code.

Shortened code

With the above advice this would shorten your code to:

public static List&lt;String&gt; removeDuplicates(List&lt;String&gt; input) {
    List&lt;String&gt; array = new ArrayList&lt;String&gt;();
    Set&lt;String&gt; noDups = new TreeSet&lt;String&gt;();
    for(int i = 0; i &lt; input.size(); i++){
        noDups.add(input.get(i));
    }
    return new ArrayList&lt;String&gt;(noDups);
}


There is however one more thing we can do, and that is to use a specific constructor of TreeSet: 

public static List&lt;String&gt; removeDuplicates(List&lt;String&gt; input) {
    return new ArrayList&lt;String&gt;(new TreeSet&lt;String&gt;(input));
}