List of unique elements, given a List of Lists

Question

Given an ArrayList transactions of sorted Integer ArrayLists, I am writing code to return its unique elements. For example, given

transactions = [
  [1, 1, 2, 3, 5, 8, 13, 21],
  [2, 3, 6, 10],
  [11, 21]
]

my code should return the unique elements, preserving sorted order:

[1, 2, 3, 5, 6, 8, 10, 11, 13, 21]

To accomplish this, I am simply adding each element in the each list to a LinkedHashSet, which by its definition keeps the sorting and removes duplicates.

Set<Integer> uniqEl = new LinkedHashSet<>();

for (List<Integer> l : transactions) {
    for (Integer n : l) {
        uniqEl.add(n);
    }
}

Although my code gets the job done by taking advantage of the Java library, I want a more efficient implementation. Any ideas for a better algorithm to produce a sorted list of unique elements from a list of lists?

Answer 1

You won't be able to have something more efficient that using a TreeSet and adding all lists into this set. A TreeSet will sort the elements by their natural ordering ascendingly and it will disregard the duplicates.

public static void main(String[] args) {
    List<List<Integer>> transactions = Arrays.asList(Arrays.asList(1, 1, 2, 3, 5, 8, 13, 21), Arrays.asList(2, 3, 6, 10), Arrays.asList(11, 21));

    SortedSet<Integer> set = new TreeSet<>();
    for (List<Integer> l : transactions) {
        set.addAll(l);
    }
}

Of course, you could use Java 8 Streams to one-line that:

SortedSet<Integer> set = transactions.stream()
                                     .flatMap(List::stream)
                                     .collect(Collectors.toCollection(TreeSet::new));

With this solution, you could run it in parallel but you would have to measure that it improves performance.