# Ace 'Remove Duplicates' Interview: Your Prep Guide You've probably seen it. The whiteboard problem where someone asks you to "remove duplicates" from a list, an array, maybe even a linked list. It sounds innocent enough, right? Like a warm-up. But I've watched countless senior candidates stumble, missing critical details that separate a hire from a "thanks for your time." This problem isn't about memorizing an algorithm; it's a litmus test for how you think, communicate, and handle constraints under pressure. This guide will help you crush it. ## The Problem Isn't the Problem: It's the Questions You Ask Most folks hear "remove duplicates" and immediately jump to hashing or sorting. That's a mistake. Your first five minutes must be spent clarifying. An interviewer throws out a vague problem statement to see if you'll blindly code or if you'll act like a responsible engineer. You wouldn't build a system without understanding requirements, so don't code without them either. Start with these foundational questions, even if you think you know the answers: * **What kind of data are we dealing with?** Is it integers, strings, custom objects? What's the range for integers? What's the maximum length for strings? Are they ASCII, Unicode? This changes everything from comparison logic to space complexity. * **What's the input structure?** Is it an array (dynamic or fixed-size?), a `List` (like Java's `ArrayList` or Python's list), a `LinkedList`, a `Set` (though if it's a `Set`, the problem's trivial), or something else? Knowing this dictates your access patterns and mutability. * **What's the desired output?** Do you need to return a *new* collection with unique elements, or modify the *original* in-place? This is a huge differentiator. In-place modification often implies a two-pointer approach or similar trickery, while a new collection is straightforward with extra space. * **What about order?** Does the relative order of the *first occurrences* of unique elements need to be preserved? Or can the output be in any order, say, sorted? This often determines whether you can use a `Set` directly or need a `LinkedHashSet`/ordered dictionary. * **What are the constraints on space and time complexity?** This is where you fish for the "gotcha." Is O(N) space acceptable? Is O(N log N) time okay, or do they want O(N)? This is the golden question that directs your algorithm choice. If they say "no extra space," you know hashing is out, and you're looking at something quadratic or an in-place sort. Let's say they give you a `List` and want an in-place modification, preserving order, with minimal extra space. Now you're talking about a completely different beast than if they just wanted a new `Set`. ## Scenario 1: The "Easy" One – New Collection, Any Order This is the simplest variation, and frankly, if this is all they ask, it's a red flag for a senior role. They're likely probing deeper later. **Problem:** Given an array of integers, `nums`, return a *new* array containing only the unique elements. The order of elements in the output doesn't matter. **Your Thought Process:** Since order doesn't matter and you're returning a new collection, you immediately think of a `HashSet` (or `std::unordered_set` in C++, `dict.fromkeys` followed by `list()` in Python). 1. **Iterate:** Loop through the input array. 2. **Add to Set:** For each element, try to add it to a `HashSet`. Sets inherently handle uniqueness. 3. **Convert Back:** Convert the `HashSet` to an array or list. **Example (Java):** ```java import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; public class RemoveDuplicatesEasy { public List removeDuplicates(List nums) { Set uniqueElements = new HashSet<>(); for (int num : nums) { uniqueElements.add(num); } return new ArrayList<>(uniqueElements); } } ``` **Complexity Analysis:** * **Time:** O(N) on average, because adding to a hash set usually takes O(1). In the worst case (hash collisions), it can degrade to O(N) per insertion, making the total O(N^2), but this is rare with good hash functions. * **Space:** O(N) in the worst case, as all elements could be unique and stored in the `HashSet`. This is your baseline. If the interviewer asks for anything more complex, it means they're testing your ability to optimize or consider constraints. ## Scenario 2: Maintaining Order – New Collection Now they've added a wrinkle. The relative order of the unique elements must be preserved. **Problem:** Given an array of integers, `nums`, return a *new* array containing only the unique elements, preserving their original relative order. **Your Thought Process:** A standard `HashSet` doesn't guarantee order. You need a data structure that combines uniqueness with ordered insertion. 1. **Ordered Set/Map:** In Java, that's a `LinkedHashSet`. In Python, `dict.fromkeys()` preserves insertion order. In C++, `std::map` or `std::set` (tree-based) maintain sorted order, but not *insertion* order if elements aren't inserted in that order. For true insertion order, you'd combine a `std::unordered_set` for fast lookups with a `std::vector` for the result. **Example (Java with `LinkedHashSet`):** ```java import java.util.ArrayList; import java.util.LinkedHashSet; import java.util.List; import java.util.Set; public class RemoveDuplicatesOrdered { public List removeDuplicates(List nums) { Set uniqueElements = new LinkedHashSet<>(); // Key difference! for (int num : nums) { uniqueElements.add(num); } return new ArrayList<>(uniqueElements); } } ``` **Example (Python with `dict.fromkeys()`):** ```python def remove_duplicates_ordered(nums: list[int]) -> list[int]: # dict.fromkeys creates a dictionary with keys from the iterable and None values # Since Python 3.7, dicts preserve insertion order. return list(dict.fromkeys(nums)) ``` **Complexity Analysis:** * **Time:** Still O(N) on average. `LinkedHashSet` operations are typically O(1). * **Space:** Still O(N) in the worst case. This is a common follow-up. Make sure you know your language's specific data structures for this. ## Scenario 3: The Tricky One – In-Place Modification, Sorted Input This is where the problem starts to feel like a proper algorithmic challenge. You're likely dealing with an array, and they want to modify *that specific array* without using much extra memory. If the input is sorted, it simplifies things significantly. **Problem:** Given a *sorted* array of integers, `nums`, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be preserved. Return the new length of the array. The elements beyond the new length don't matter. **Your Thought Process:** "In-place" and "minimal extra space" immediately scream two-pointers. Since it's sorted, duplicates will always be adjacent. 1. **Two Pointers:** Initialize a `write_pointer` (or `slow`) to 0, which tracks where the next unique element should go. Initialize a `read_pointer` (or `fast`) to 1, which iterates through the array. 2. **Compare:** If `nums[read_pointer]` is different from `nums[write_pointer]`, it means we've found a new unique element. Increment `write_pointer` and then copy `nums[read_pointer]` to `nums[write_pointer]`. 3. **Skip Duplicates:** If `nums[read_pointer]` is the same as `nums[write_pointer]`, it's a duplicate. Just increment `read_pointer` and keep looking. 4. **Result:** The `write_pointer` (plus one, for 0-indexing) will be the new length. **Example (Java):** ```java public class RemoveDuplicatesSortedInPlace { public int removeDuplicates(int[] nums) { if (nums.length == 0) { return 0; } int writePointer = 0; // Pointer for the next unique element position for (int readPointer = 1; readPointer < nums.length; readPointer++) { if (nums[readPointer] != nums[writePointer]) { writePointer++; // Move writePointer forward nums[writePointer] = nums[readPointer]; // Place the unique element } // If nums[readPointer] == nums[writePointer], it's a duplicate, // we just advance readPointer and effectively skip it. } return writePointer + 1; // The new length } } ``` **Complexity Analysis:** * **Time:** O(N), as both pointers traverse the array at most once. * **Space:** O(1), since you're modifying in-place with only a few extra variables. This specific problem is a LeetCode classic (problem 26). Don't just regurgitate the solution; explain *why* two pointers work so well here due to the sorted nature. ## Scenario 4: The Hardest One – In-Place, Unsorted Input, O(1) Space This is the true test. If they ask for "in-place" and "O(1) extra space" on an *unsorted* input, they're looking for cleverness or a trade-off. **Problem:** Given an *unsorted* array of integers, `nums`, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements is *not* important. Return the new length. **Your Thought Process:** Unsorted, in-place, O(1) space, order doesn't matter. This immediately suggests sorting the array first as a preprocessing step. Why? Because once sorted, you can apply the two-pointer technique from Scenario 3. 1. **Sort:** Sort the array. This changes the order, but the problem statement says order doesn't matter. 2. **Two Pointers:** Apply the two-pointer approach from Scenario 3 to the now-sorted array. **Example (Java):** ```java import java.util.Arrays; public class RemoveDuplicatesUnsortedInPlace { public int removeDuplicates(int[] nums) { if (nums.length == 0) { return 0; } // Step 1: Sort the array. This changes the order, but the problem allows it. Arrays.sort(nums); // This is typically O(N log N) // Step 2: Apply the two-pointer technique from the sorted in-place problem. int writePointer = 0; for (int readPointer = 1; readPointer < nums.length; readPointer++) { if (nums[readPointer] != nums[writePointer]) { writePointer++; nums[writePointer] = nums[readPointer]; } } return writePointer + 1; } } ``` **Complexity Analysis:** * **Time:** O(N log N) dominated by the sorting step. * **Space:** O(1) if the sort is in-place (like `Arrays.sort` for primitives in Java, depending on implementation specifics, or `std::sort` in C++). Some sorting algorithms might use O(log N) or O(N) auxiliary space, but for an interview, assume the standard library sort is efficient enough in space unless explicitly challenged. **Caveat:** This solution fundamentally changes the order of elements. If the interviewer *then* says, "Actually, preserve the relative order," you have a problem. At that point, you must use a `HashSet` or equivalent for tracking seen elements, which means O(N) space. There's no O(1) space, in-place, order-preserving solution for an *unsorted* array in general *without specific value range constraints* that allow for a boolean array or similar. This is a critical trade-off to discuss. Always clarify assumptions. What if they insisted on O(1) space *and* original relative order *and* unsorted? That's almost impossible without specific constraints on the numbers themselves (e.g., numbers are all small positive integers, allowing a boolean array for seen values, which is technically O(1) *if* the range is fixed and small). If they throw this at you, it's either a trick question or they expect you to point out the impossibility without relaxing one of the constraints. Don't be afraid to say, "Given these three constraints, an efficient solution isn't generally possible without specific additional information about the data." ## Scenario 5: When Elements Are Objects, Not Primitives You've handled integers, but what if it's `List`? **Problem:** Given a `List`, remove duplicate `Person` objects. **Your Thought Process:** This immediately brings up the concept of equality. For primitives, `==` works. For objects, `==` compares references. You need to define what "duplicate" means for your custom object. 1. **Equality Definition:** You must override `equals()` and `hashCode()` in your `CustomObject` class. * `equals()`: Defines when two objects are logically the "same." For a `Person` object, it might be based on `id` or a combination of `firstName` and `lastName`. * `hashCode()`: Essential for `HashSet`/`HashMap` performance. If two objects are equal, their hash codes *must* be the same. If hash codes differ for equal objects, you'll get duplicates in hash-based collections. 2. **Apply Previous Techniques:** Once `equals()` and `hashCode()` are properly implemented, you can apply any of the previous techniques (using `HashSet`, `LinkedHashSet`, etc.) as if they were primitives. **Example (`Person` Class in Java):** ```java import java.util.Objects; class Person { int id; String name; public Person(int id, String name) { this.id = id; this.name = name; } @Override public boolean equals(Object o) { if (this == o) return true; // Same instance if (o == null || getClass() != o.getClass()) return false; // Different type or null Person person = (Person) o; // Cast return id == person.id; // Equality based on ID } @Override public int hashCode() { return Objects.hash(id); // Hash based on ID } @Override public String toString() { return "Person{" + "id=" + id + ", name='" + name + '\'' + '}'; } } // Then, the removal code would look familiar: public class RemoveDuplicatesObjects { public List removeDuplicates(List people) { Set uniquePeople = new LinkedHashSet<>(); // If order matters for (Person p : people) { uniquePeople.add(p); } return new ArrayList<>(uniquePeople); } } ``` **Key Takeaway:** If your problem involves custom objects, immediately ask how equality is defined. Your `equals()` and `hashCode()` implementations are crucial here. If you don't implement them correctly, your deduplication logic will fail silently. ## Scenario 6: The `k` Duplicates Problem (Follow-up) A common follow-up: "What if I want to keep elements that appear at most `k` times?" **Problem:** Given an array, `nums`, remove all elements that appear more than `k` times. Keep the order of the remaining elements. **Your Thought Process:** You need to count occurrences. A `HashMap` (or `dict` in Python) is perfect for this. 1. **Count Frequencies:** Iterate through the input array and store the frequency of each element in a `HashMap`. 2. **Filter and Build New List:** Iterate through the original array *again*. For each element, check its count in the map. If the count is `<= k`, add it to a new result list. **Example (Java):** ```java import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class RemoveKDuplicates { public List removeDuplicatesKeepK(List nums, int k) { Map counts = new HashMap<>(); for (int num : nums) { counts.put(num, counts.getOrDefault(num, 0) + 1); } List result = new ArrayList<>(); for (int num : nums) { if (counts.get(num) <= k) { // Check if its total count is <= k result.add(num); } } return result; } } ``` **Complexity Analysis:** * **Time:** O(N) for both passes (counting and filtering). * **Space:** O(N) for the `HashMap` in the worst case (all unique elements) and O(N) for the `result` list. This problem specifically asks to *keep* elements that appear at most `k` times. LeetCode 80, "Remove Duplicates from Sorted Array II," is a variation where you keep at most two occurrences *in-place* for a sorted array, which again uses a two-pointer approach, but with a slightly more complex condition. Understand the subtle differences in these problem statements. ## Your Pre-Interview Checklist for "Remove Duplicates" Before any interview, refresh these points: 1. **Know Your Language's Collections:** * `HashSet` vs. `LinkedHashSet` vs. `TreeSet` (Java) * `set` vs. `dict` (Python) * `std::unordered_set` vs. `std::set` (C++) 2. **Master Two-Pointers:** Especially for in-place modifications on sorted arrays. Practice LeetCode 26 and 80. 3. **Understand `equals()` and `hashCode()`:** Crucial for object deduplication. 4. **Complexity Analysis (Time & Space):** Always be ready to articulate this. 5. **Practice Asking Clarifying Questions:** This is non-negotiable. Write down the questions above and internalize them. Your first three minutes should be dedicated to this. 6. **Edge Cases:** What about an empty array? An array with one element? An array where all elements are the same? Test your code with these. You'll see "remove duplicates" in various guises – arrays, linked lists, strings. The core principles of identifying duplicates, handling order, and managing space/time constraints remain constant. Don't just solve the problem; demonstrate your engineering maturity. ## Ready to Ace Your Next Interview? Practice with AI-powered [mock interview](/en/interview-prep)s tailored to your target role and company. [Start Practicing for Free](/sign-up) | [Explore Interview Prep](/en/interview-prep)