List algorithms: duplicates, intersection, difference and partition

For this lesson, we'll focus on the algorithms that come up most in Java interviews and code reviews: deduplication, duplicate counting, finding all duplicates, intersection, difference, symmetric difference and chunk partitioning. We'll use Java 21 collections and streams, and we'll be explicit about whether an algorithm treats the input as a set or as a multiset. The difference is not academic: [A, A, B] and [A, B, B] contain the same distinct values, but they are not the same bag of values.

01Picture it first: coloured regions and shipment boxes

Think of two lists as two trays of labels. A set-style intersection asks "which labels appear in both trays at least once?" A multiset intersection asks "how many copies can I match from both trays?" Chunking is a separate move: packing a long row of labels into boxes of size 3 or 500 without changing the labels inside.

The diagram shows both ideas because they are the two mental models I use in interviews.

Fig. 1

A Venn-style diagram shows left-only, intersection and right-only regions, and a second row shows a list split into chunks of size three

The important split is membership versus counts. If the problem says unique values, sets are natural. If it says orders, payments, seats or log lines, ask whether duplicates are meaningful before you choose the algorithm.

02Removing duplicates under the hood

The cleanest order-preserving dedupe is a LinkedHashSet. HashSet keeps uniqueness but does not promise iteration order; LinkedHashSet adds a linked order through entries, so iteration follows first insertion.

List<String> importedIds = List.of("P-10", "P-20", "P-10", "P-30", "P-20");

List<String> uniqueInOrder = new ArrayList<>(new LinkedHashSet<>(importedIds));
System.out.println(uniqueInOrder);       // [P-10, P-20, P-30]

List<String> viaStream = importedIds.stream()
    .distinct()
    .toList();
System.out.println(viaStream);           // [P-10, P-20, P-30]

Both versions use equals and hashCode. The loop is O(n) expected time and O(u) space, where u is the number of distinct values. stream().distinct() is nice when you are already in a stream pipeline, but it returns an unmodifiable list with toList() on Java 16+, so use collect(Collectors.toCollection(ArrayList::new)) if you need to mutate the result.

Dedupe by key is the version production code asks for. Two Order objects may differ in timestamp or status, but the import rule might say "keep the first order per external ID." In that case, store keys in a set and keep the element when the key was not seen before.

record Order(String externalId, String status, Instant receivedAt) { }

static <T, K> List<T> distinctByKey(List<T> values, Function<T, K> key) {
    Set<K> seenKeys = new HashSet<>();
    List<T> result = new ArrayList<>();
    for (T value : values) {
        if (seenKeys.add(key.apply(value))) {
            result.add(value);
        }
    }
    return result;
}

Notice that the key can be different from object equality. That is useful, but it also means you must name the rule clearly. "Unique orders" and "unique order IDs" are not the same requirement.

03Counting duplicates and avoiding the frequency trap

Counting is a map problem. The key is the list element, and the value is how many times you saw it. Streams can express this with groupingBy and counting, while a loop can use merge.

List<String> statuses = List.of("NEW", "PAID", "NEW", "FAILED", "PAID", "PAID");

Map<String, Long> counts = statuses.stream()
    .collect(Collectors.groupingBy(
        Function.identity(),
        LinkedHashMap::new,
        Collectors.counting()
    ));

counts.entrySet().stream()
    .filter(entry -> entry.getValue() > 1)
    .forEach(System.out::println);       // NEW=2, PAID=3

The LinkedHashMap::new supplier keeps keys in first-seen order. Without it, groupingBy typically uses a HashMap, and the iteration order is not part of the contract.

Here is the loop version I write when I want validation or side effects nearby:

Map<String, Integer> counts = new LinkedHashMap<>();
for (String status : statuses) {
    counts.merge(status, 1, Integer::sum);
}

Both approaches are O(n) expected time and O(u) space. Collections.frequency(list, x) is fine for one value because it scans once. The trap is calling it once per distinct element or, worse, once per original element.

List<String> values = List.of("A", "B", "A", "C", "B", "A");
Set<String> unique = new LinkedHashSet<>(values);

for (String value : unique) {
    System.out.println(value + "=" + Collections.frequency(values, value));
}

That example is O(n*u). If every element is unique, u is n, so it becomes O(n²). For 100,000 unique values, that means about 10,000,000,000 equality checks in the worst shape. Build one frequency map instead.

04Finding all duplicates

To find duplicate values, use two sets: one for values already seen, and one for values confirmed as duplicates. Set.add returns false when the value was already present, which gives you the whole algorithm.

static <T> Set<T> duplicatesOf(List<T> values) {
    Set<T> seen = new HashSet<>();
    Set<T> duplicates = new LinkedHashSet<>();
    for (T value : values) {
        if (!seen.add(value)) {
            duplicates.add(value);
        }
    }
    return duplicates;
}

System.out.println(duplicatesOf(List.of("A", "B", "A", "C", "B", "A")));
// [A, B]

This returns each duplicate value once, in the order it first became a duplicate. It is O(n) expected time and O(u) space. If you need duplicate positions, store indexes in a Map<T, List<Integer>>; if you need counts, use the frequency map from the previous section.

null works with HashSet and LinkedHashSet, so this algorithm can find repeated nulls in a mutable list. List.of cannot contain nulls, so the question only appears with mutable or external inputs.

05Intersection: set style and multiset style

A set-style intersection returns values that appear in both lists at least once. The simplest mutable-list version is copy left, then retainAll(rightMembership). The key is to make the membership side a HashSet first.

List<String> left = List.of("A", "B", "C", "A");
List<String> right = List.of("B", "C", "D");

Set<String> rightSet = new HashSet<>(right);      // O(m)
List<String> intersection = new ArrayList<>(left);
intersection.retainAll(rightSet);                 // O(n) expected membership tests

System.out.println(intersection);                 // [B, C]

The result above preserves the order and duplicates from the left side for values that are in the right set. If left were [B, B, C], the result would be [B, B, C], because this is membership filtering, not duplicate matching.

Passing a List as the argument can make retainAll O(n*m), because each membership check may scan the argument list. Passing a HashSet makes it O(n + m) expected time and O(m) extra space.