Write a Java method to remove duplicates from a list while keeping the original order.
Put the elements into a LinkedHashSet, which drops repeats and remembers first-seen order, then copy it back into a list. It takes O(n) time and O(n) space.
Explain it simply
A plain HashSet removes duplicates but scrambles order. A LinkedHashSet does the same and keeps the order in which elements first arrived.
Line by line
import java.util.*;
public static <T> List<T> unique(List<T> input) {
return new ArrayList<>(new LinkedHashSet<>(input));
}
// List<Integer> data = List.of(4, 2, 4, 7, 2, 9);
// unique(data) returns [4, 2, 7, 9]The LinkedHashSet constructor adds elements one by one. Each repeat is rejected by equals and hashCode, so only the first copy of 4 and 2 survives. The ArrayList constructor then copies the survivors in order.
A manual version, if the interviewer asks you not to use a ready-made set trick:
public static List<Integer> uniqueManual(List<Integer> input) {
Set<Integer> seen = new HashSet<>();
List<Integer> out = new ArrayList<>();
for (int x : input) {
if (seen.add(x)) out.add(x); // add() is true only for new values
}
return out;
}Complexity
Time O(n) on average, space O(n).
What to say in the interview
"I use LinkedHashSet for order-preserving de-duplication. The elements need correct equals and hashCode. With streams the same thing is list.stream().distinct().toList()."
Common mistakes
- Using HashSet and getting a different order.