Removing duplicates without using a temporary buffer

Question

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<Integer> list = new LinkedList<Integer>();
        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<Integer> 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);
    }
}

Answer 1

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<Integer> list = new LinkedList<Integer>();
    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<Integer> list = new LinkedList<Integer>();

    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 <T extends Comparable<? super T>> void removeDuplicates(List<T> list) {
    Collections.sort(list);

    Iterator<T> 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 <T extends Comparable<? super T>>? 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.

Answer 2

    LinkedList<Integer> list = new LinkedList<Integer>();
    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);

I consider this a long and tedious way of adding data to a list. A LinkedList, just like many other collections in Java, has a copy-constructor where it can take another list as argument. This makes it possible to write a much shorter way to setup your list:

LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(9, 1, 3, 2, 5, 7, 8, 3, 1, 8));

Answer 3

The algorithm you have used has me a little confused. You have sorted the data in-place in the input List. Don't get me wrong, this is a useful thing to do, but I am not sure it is in the spirit of the question.... though, it can be interpreted that way.

Assuming your data is sorted, consider the following:

Integer previous = null;
boolean first = true;
for (Iterator<Integer> iterator = list.listIterator(); iterator.hasNext();) {
    Integer current = iterator.next();
    if (!first && Objects.equals(current, previous)) {
        iterator.remove();
    }
    first = false;
    previous = current;
}

Essentially, iterate through the (sorted) items, and if the item is the same as the previous item, ignore it. This is very similar to Brythan's solution (which gets a +1 from me), but note the different way I handle the first element in the list, compared to him.

If the list is not sorted, and you cannot have buffer, then the best system to use would be the ListIterator, and not the plain Iterator. You have much more flexibility with that....

for (ListIterator listIt = list.listIterator(list.size()); listIt.hasPrevious();) {
    Integer current = listIt.previous();
    listIt.next(); // make the iterator go forward again....
    while (listIt.hasNext()) {
        Integer following = listIt.next();
        if (Objects.equals(current, following) {
            listIt.remove(); // remove the matching following items...
            break; // no more matches expected.
        }
    }
    // move forward again to our current position....
    do {
        forward = listIt.previous();
    } while (!Objects.equals(current, forward));
}

The above will remove all 'following' items in the list that are equal to any item prior to them.

Note the iterator goes from the end to the beginning. For each item in the list, it scans forward from there to see if there's a match.

This is an \$O(n^2)\$ operation, and is slower as a result, but it does not require sorting the data.