2 ms·
Great exercise! Here's my solution in Java, seems be about O(n): class Ptr { public Ptr next; } <T> List<List<T>> mergeIntersecting(Li
by cousin_it 10y ago
Great exercise! Here's my solution in Java, seems be about O(n):
class Ptr {
public Ptr next;
}
<T> List<List<T>> mergeIntersecting(List<List<T>> lists) {
Map<T, Ptr> lookup = new HashMap<>();
Map<Ptr, List<T>> output = new HashMap<>();
for (List<T> list : lists) {
Ptr ptr = new Ptr();
if (list.isEmpty()) {
output.put(ptr, new ArrayList<>());
}
for (T value : list) {
Ptr prev = lookup.get(value);
lookup.put(value, ptr);
while (prev != null && prev != ptr) {
Ptr tmp = prev.next;
prev.next = ptr;
prev = tmp;
}
}
}
for (Map.Entry<T, Ptr> entry : lookup.entrySet()) {
Ptr ptr = entry.getValue();
while (ptr.next != null) {
ptr = ptr.next;
}
if (!output.containsKey(ptr)) {
output.put(ptr, new ArrayList<>());
}
output.get(ptr).add(entry.getKey());
}
return new ArrayList<>(output.values());
}
If I give it random lists of integers, it takes around 1 microsecond per element of input. Really curious if there's any way to speed it up a lot.