Removing duplicates without using a temporary buffer This question is from Cracking the Coding Interview and in this question they have asked to solve without using temporary buffer.

I have used Iterator interface. Can I use it or need to re-implement it?

import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;

public class WithoutExtraSpace {

    public static void main(String[] args) {

        LinkedList&lt;Integer&gt; list = new LinkedList&lt;Integer&gt;();
        list.add(9);
        list.add(1);
        list.add(3);
        list.add(2);
        list.add(5);
        list.add(7);
        list.add(8);
        list.add(3);
        list.add(1);
        list.add(8);
        System.out.println(list);
        Collections.sort(list);
        System.out.println(list);

        Iterator&lt;Integer&gt; itr = list.iterator();
        if (itr.hasNext()) {
            Integer previous = itr.next();
            while (itr.hasNext()) {
                Integer current = itr.next();
                if (previous.equals(current)) {
                    itr.remove();
                }
                previous = current;
            }
        }
        System.out.println(list);
    }
}
public class WithoutExtraSpace {


Class names should reflect what the class does.  In this case, I would expect a name like ListUtilities or even CrackingTheCodingInterviewExercise.  It's not clear to me what WithoutExtraSpace even means.  Perhaps a reference to the lack of a temporary buffer?  Then it should have been DuplicateRemoverWithoutExtraSpace.  Or just DuplicateRemover.  

    LinkedList&lt;Integer&gt; list = new LinkedList&lt;Integer&gt;();
    list.add(9);
    list.add(1);
    list.add(3);
    list.add(2);
    list.add(5);
    list.add(7);
    list.add(8);
    list.add(3);
    list.add(1);
    list.add(8);
    System.out.println(list);


I'd add some whitespace in this section:

    List&lt;Integer&gt; list = new LinkedList&lt;Integer&gt;();

    list.add(9);
    list.add(1);
    list.add(3);
    list.add(2);
    list.add(5);
    list.add(7);
    list.add(8);
    list.add(3);
    list.add(1);
    list.add(8);

    System.out.println("Unsorted:  " + list);


Now I have a declaration block, an initialization block, and the start of the coding block.  

I changed the declaration of list.  Instead of being of type LinkedList, I made it of type List, which is the interface name.  This is why we have things that implement interfaces, so we don't have to care what the implementation is.  You happen to be using a LinkedList, but if you change that to an ArrayList or any other implementation, it shouldn't matter.  

I added an "Unsorted:" at the beginning of the println.  When I first ran this, I didn't know what the various outputs were.  Now I do.  

Avoid code in main

You put a lot of your code in the main method itself.  As a general rule, there should be very little code in main.  Process the arguments, perhaps initialize variables, and then call methods to do the heavy lifting.  This allows you to reuse those pieces that do actual work.  If all the code is in main, then you have to edit main to use it.  Further, you can't just add your class to another project; you'd have to copy the code itself.  

    removeDuplicates(list);

    System.out.println("Unique:  " + list);


This is the remainder of the main method.  Now let's work on removeDuplicates.  

public static &lt;T extends Comparable&lt;? super T&gt;&gt; void removeDuplicates(List&lt;T&gt; list) {
    Collections.sort(list);

    Iterator&lt;T&gt; itr = list.iterator();
    if (itr.hasNext()) {
        T previous = itr.next();

        while (itr.hasNext()) {
            T current = itr.next();

            if (previous.equals(current)) {
                itr.remove();
            } else {
                previous = current;
            }
        }
    }
}


Rather than lock us into a single implementation, let's use generics to allow us to cover a wide variety of possible types.  Why &lt;T extends Comparable&lt;? super T&gt;&gt;?  The short answer is that's what made my IDE happy.  The reason why it made the IDE happy is that Collections.sort uses it.  So we're basically saying that removeDuplicates will work with any List type that we can sort.  

Everywhere in this section of code that used to say Integer now says T instead.  

            if (previous.equals(current)) {
                itr.remove();
            }
            previous = current;


I changed this to 

            if (previous.equals(current)) {
                itr.remove();
            } else {
                previous = current;
            }


My reasoning is that when we just removed current from the List, why should we be comparing it to other elements?  It's already gone and we shouldn't remove other elements based on something that is no longer in the List.  Note that this has no functional impact, as we know that previous and current are equal if we just removed current.  But I find it easier to follow, and it avoids an unnecessary assignment.  The new logic is that we either remove current from the list (as a duplicate) or we update previous (since there are no more duplicates of it, we need to start looking for duplicates of current).  We don't do both at once. 

    System.out.println(list);


I removed the display of the sorted with duplicates list.  It seems more like debugging code than code necessary to solve the problem.  As such, it should be removed before turning in the code for review.  

Your Question


  I have used Iterator interface. Can I use it or need to re-implement it?


I don't know the answer to this.  For a definitive answer, you'd have to ask the interviewer.  If you told us what the book actually says, we might be able to give you some guidance.  

As a general rule, it's good to ask the interviewer questions that show you understand the problem.  Asking if it is all right to use the iterator() method of List is perfectly reasonable.  

Another question that is relevant here is if you are allowed to change the existing order of the List.  Clearly it must be mutable, as you have to remove duplicates.  It's not as clear that order doesn't matter.  It might or might not.  

Complexity

Collections.sort is an \$O(n \log n)\$ algorithm in terms of time.  The rest of the method is linear (\$O(n)\$) in time.  You iterate through list once.  This makes the method \$O(n \log n)\$ overall.  

In terms of memory complexity, the iteration is \$O(1)\$.  It adds three variables, regardless of the size of list.  The sort is more complex.  It can use up to \$n/2\$ new object references.  That makes it \$O(n)\$ in memory complexity.  This might be a violation of the "no temporary buffer" constraint.  

Testing

It looks like you tested this code in place in the main method.  It probably would have been better if you could have written this as unit tests.  As it is, each new test obliterates the old.