Cracking The Coding Interview Together – Problem 2.1: Remove Dups

Alright, let’s continue the Cracking The Coding Interview — Together series.

This one looks innocent at first glance. Linked list. Duplicates. Remove them. Easy, right?
And then the interviewer calmly adds:

“Follow up: what if you are not allowed to use any temporary buffer?”

That’s usually the moment when candidates either light up… or quietly panic.
Let’s make sure you’re in the first group.

As always, let’s follow our ritual.

Let’s get into today's problem! We always follow the format as follows

1. Understand the problem statement together
2. Ask any questions, that you would like to ask the interviewer
3. I would urge you to take your time here and try to come up with your own solution before going forward
4. Think how you would go about solving the problem(you would be talking out loud in front of the actual interviewer)
5. Write code and understand how it works and explain it to your interviewer

Problem statement

Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?

Analyse the problem statement together

The problem says:

Remove Dups: Write code to remove duplicates from an unsorted linked list.

A few important words here that we should not gloss over:

• Linked list (not an array)
• Unsorted
• Remove duplicates (keep one occurrence)
• And later… no temporary buffer

So what does this actually mean?

If we are given a linked list like:

3 → 1 → 4 → 3 → 2 → 1 → 4

The result should be something like:

3 → 1 → 4 → 2

Important observations:

• The order does not have to change, unless explicitly stated.
• We are not creating a new list; we are modifying the existing one.
• We are not told to return the list, just to remove duplicates.

And because the list is unsorted, we cannot rely on adjacent nodes being equal.

Before even thinking about code, pause here.
This is already very different from removing duplicates in an array.

Questions for the interviewer

This step is extremely important, and I’ll repeat it in every post because people skip it far too often.

If you were sitting in an interview, these are the questions I would personally ask:

1. Can the linked list be empty or null?
   • If yes, what should we return?
2. Do we need to preserve the original order of elements?
   • Usually yes, but it’s worth confirming.
3. What exactly does “remove duplicates” mean?
   • Keep the first occurrence and remove the rest? (Most likely)
4. Are we allowed to use extra memory?
   • The main question says nothing.
   • The follow-up explicitly says no temporary buffer.
5. Is this a singly linked list or doubly linked list?
   • This matters for pointer manipulation.

Let’s assume the interviewer gives us these answers:

• The list can be null or empty.
• Preserve the original order.
• Keep the first occurrence.
• Yes, you can use extra memory for the first solution.
• Singly linked list.

Good. Now we can move forward confidently.

Think about the Solution

Please do not jump to code yet.

This problem is not about syntax.
It is about trade-offs.

You should already be thinking:

• How do I detect duplicates efficiently?
• What data structure helps me remember what I’ve already seen?
• What happens when I’m not allowed to remember anything?

Let’s explore both cases step by step.

First thought (with extra memory)

When I hear duplicates, my brain immediately goes to:

• HashSet
• HashMap

Because checking membership in a hash-based structure is O(1) on average.

The idea would be:

• Traverse the linked list.
• Keep a HashSet of values we have already seen.
• If the current node’s value is already in the set → remove the node.
• Otherwise → add the value to the set and move on.

This feels clean, simple, and efficient.

But before we settle, let’s think about the follow-up.

Second thought (without extra memory)

Now the interviewer takes away your HashSet.

No arrays.
No sets.
No maps.

You’re left with just:

• The linked list
• Pointers
• Your brain

So how do you detect duplicates without remembering what you’ve seen?

The answer is:

You compare the current node with every node that comes after it.

Yes — nested loops.
Yes — slower.
But completely valid.

This is a classic runner technique:

• One pointer (current) moves forward one node at a time.
• Another pointer (runner) scans the rest of the list and deletes any duplicates of current.

This is where interviewers really see how comfortable you are with pointer manipulation.

Write code and explain

Let’s start with the simpler and more practical solution.

Solution 1: Using a buffer

Intuition

• We keep track of all values we have seen so far.
• As we move through the list, we check if the current value already exists.
• If yes → skip the node.
• If no → store it and continue.

Java code

public static void removeDuplicates(Node head) {
    if (head == null) return;

    HashSet<Integer> seen = new HashSet<>();
    Node current = head;
    Node previous = null;

    while (current != null) {
        if (seen.contains(current.data)) {
            // Duplicate found, remove current node
            previous.next = current.next;
        } else {
            seen.add(current.data);
            previous = current;
        }
        current = current.next;
    }
}

Now the follow-up: no temporary buffer allowed

This is where things get interesting.

Take a deep breath before starting this part in an interview.
Rushing here almost always leads to bugs.

Since we cannot store seen values, we must compare nodes directly.

The strategy:

• Pick one node (current).
• Scan the rest of the list using another pointer (runner).
• Remove any nodes that match current.

Then move current forward and repeat.

Intuition

• For each node, eliminate all future duplicates of that node.
• By the time we move to the next node, everything before it is guaranteed unique.

Java code

public static void removeDuplicatesNoBuffer(Node head) {
    Node current = head;

    while (current != null) {
        Node runner = current;

        while (runner.next != null) {
            if (runner.next.data == current.data) {
                // Remove duplicate
                runner.next = runner.next.next;
            } else {
                runner = runner.next;
            }
        }

        current = current.next;
    }
}

Time & Space Complexity (and why this matters)

Let’s be very clear here, because interviewers love this comparison.

Without buffer

• Time Complexity: O(n²)
  • For each node, we scan the rest of the list.
• Space Complexity: O(1)
  • No extra memory used.

With buffer

• Time Complexity: O(n)
• Space Complexity: O(n)

This is the core trade-off of this problem:

Time vs Space

And this is exactly what the interviewer wants you to articulate out loud.

Final Thoughts

This problem is not really about linked lists.

It’s about:

• Recognizing patterns
• Understanding constraints
• Communicating trade-offs clearly

If you can solve this confidently, you are already doing better than a large percentage of candidates.

As always, I strongly encourage you to:

• Try implementing both solutions yourself
• Break them
• Fix them
• Explain them out loud

That’s how real interview confidence is built.

I’ll see you in the next one.
Until then - Happy Coding!