Constraints

• 1 <= number of lists <= 200000, but your algorithm should also handle empty input.
• The total number of raw items across all iterables can be up to 5000000.
• Items are case-sensitive strings.
• Duplicates within the same list must be ignored.

Examples

Solution

def solution(lists_by_name):
    from collections import defaultdict

    item_to_lists = defaultdict(list)
    membership_count = 0

    for name, items in lists_by_name.items():
        unique_items = set(items)
        membership_count += len(unique_items)
        for item in unique_items:
            item_to_lists[item].append(name)

    pair_counts = defaultdict(int)
    pair_updates = 0

    for names in item_to_lists.values():
        names = sorted(names)
        m = len(names)
        pair_updates += m * (m - 1) // 2
        for i in range(m):
            for j in range(i + 1, m):
                pair_counts[(names[i], names[j])] += 1

    sorted_pairs = [(a, b, count) for (a, b), count in sorted(pair_counts.items())]
    return {
        'membership_count': membership_count,
        'unique_item_count': len(item_to_lists),
        'pair_updates': pair_updates,
        'pair_counts': sorted_pairs
    }

Time complexity: O(M + sum_i C(f_i, 2)), where M is the number of distinct (list, item) memberships after deduplication and f_i is the number of lists containing item i.. Space complexity: O(M + U + P), where U is the number of unique items and P is the number of pairs with positive overlap..

Hints

1. First deduplicate each individual list, then think item -> lists that contain it.
2. If one item appears in f different lists, it contributes C(f, 2) pair updates.

Constraints

• 1 <= number of lists <= 200000, but your function should also handle 0 or 1 list.
• The total number of raw items across all iterables can be up to 5000000.
• Items are case-sensitive strings.
• An O(N^2) all-pairs comparison is not acceptable for large inputs.

Examples

Solution

def solution(lists_by_name):
    from collections import defaultdict

    names = sorted(lists_by_name)
    if len(names) < 2:
        return None

    item_to_lists = defaultdict(list)
    sizes = {}
    empty_names = []

    for name in names:
        unique_items = set(lists_by_name[name])
        sizes[name] = len(unique_items)
        if not unique_items:
            empty_names.append(name)
        for item in unique_items:
            item_to_lists[item].append(name)

    pair_counts = defaultdict(int)
    for holders in item_to_lists.values():
        holders.sort()
        for i in range(len(holders)):
            a = holders[i]
            for j in range(i + 1, len(holders)):
                b = holders[j]
                pair_counts[(a, b)] += 1

    best = None  # (overlap, jaccard, a, b)
    for (a, b), inter in pair_counts.items():
        union = sizes[a] + sizes[b] - inter
        jaccard = 1.0 if union == 0 else inter / union
        if (
            best is None or
            inter > best[0] or
            (inter == best[0] and (jaccard > best[1] or (jaccard == best[1] and (a, b) < (best[2], best[3]))))
        ):
            best = (inter, jaccard, a, b)

    if best is not None:
        return (best[2], best[3], best[0], best[1])

    if len(empty_names) >= 2:
        return (empty_names[0], empty_names[1], 0, 1.0)

    return (names[0], names[1], 0, 0.0)

Time complexity: O(M + sum_i C(f_i, 2) + P), where M is the number of distinct memberships after deduplication, f_i is the number of lists containing item i, and P is the number of distinct pairs with positive overlap.. Space complexity: O(M + U + P), where U is the number of unique items..

Hints

1. Use an inverted index item -> list names to count only pairs that actually share at least one item.
2. If no pair shares an item, handle the zero-overlap case separately.

Constraints

• 1 <= number of lists <= 200000, but your solution should also handle empty input.
• The total number of raw items across all iterables can be up to 5000000.
• Items are case-sensitive strings.
• Only pairs with overlap_count > 0 should appear in the result.

Examples

Solution

def solution(lists_by_name, k):
    from collections import defaultdict
    import heapq

    if k <= 0:
        return []

    item_to_lists = defaultdict(list)
    sizes = {}

    for name, items in lists_by_name.items():
        unique_items = set(items)
        sizes[name] = len(unique_items)
        for item in unique_items:
            item_to_lists[item].append(name)

    pair_counts = defaultdict(int)
    for holders in item_to_lists.values():
        holders.sort()
        for i in range(len(holders)):
            a = holders[i]
            for j in range(i + 1, len(holders)):
                b = holders[j]
                pair_counts[(a, b)] += 1

    if not pair_counts:
        return []

    def ranked_candidates():
        for (a, b), inter in pair_counts.items():
            union = sizes[a] + sizes[b] - inter
            jaccard = inter / union
            yield (-inter, -jaccard, a, b, inter, jaccard)

    top = heapq.nsmallest(k, ranked_candidates())
    return [(a, b, inter, jaccard) for _, _, a, b, inter, jaccard in top]

Time complexity: O(M + sum_i C(f_i, 2) + P log k), where M is the number of distinct memberships after deduplication, f_i is the number of lists containing item i, and P is the number of distinct pairs with positive overlap.. Space complexity: O(M + U + P + k), where U is the number of unique items..

Hints

1. First compute positive-overlap pair counts using an inverted index.
2. A heap of size k can avoid fully sorting every candidate pair.

Constraints

• 1 <= number of updates <= 300000, but your solution should also handle empty input.
• Each update is a pair (list_name, item).
• A duplicate update for an already-present (list_name, item) must not change the state.
• A fully recomputed all-pairs scan after every update is too slow.

Examples

Solution

def solution(updates):
    from collections import defaultdict
    import heapq

    list_items = {}
    list_sizes = defaultdict(int)
    item_lists = defaultdict(set)
    pair_overlap = {}
    neighbors = defaultdict(set)
    bucket_heaps = defaultdict(list)
    max_overlap = 0

    seen_lists = set()
    smallest_two = []

    def add_name(name):
        if name in seen_lists:
            return
        seen_lists.add(name)
        if len(smallest_two) < 2:
            smallest_two.append(name)
            smallest_two.sort()
        else:
            if name < smallest_two[0]:
                smallest_two[1] = smallest_two[0]
                smallest_two[0] = name
            elif name < smallest_two[1]:
                smallest_two[1] = name

    def pair_key(a, b):
        return (a, b) if a < b else (b, a)

    def push_current_entry(a, b):
        inter = pair_overlap[(a, b)]
        union = list_sizes[a] + list_sizes[b] - inter
        jaccard = inter / union
        heapq.heappush(bucket_heaps[inter], (-jaccard, a, b, list_sizes[a], list_sizes[b]))

    def current_best():
        nonlocal max_overlap
        while max_overlap > 0:
            heap = bucket_heaps[max_overlap]
            while heap:
                neg_j, a, b, sa, sb = heap[0]
                if pair_overlap.get((a, b), 0) != max_overlap or list_sizes[a] != sa or list_sizes[b] != sb:
                    heapq.heappop(heap)
                else:
                    inter = max_overlap
                    union = list_sizes[a] + list_sizes[b] - inter
                    return (a, b, inter, inter / union)
            max_overlap -= 1

        if len(seen_lists) < 2:
            return None
        return (smallest_two[0], smallest_two[1], 0, 0.0)

    answers = []

    for name, item in updates:
        if name not in list_items:
            list_items[name] = set()
            add_name(name)

        if item in list_items[name]:
            answers.append(current_best())
            continue

        shared_with = set(item_lists[item])

        list_items[name].add(item)
        list_sizes[name] += 1

        for other in list(neighbors[name]):
            if other not in shared_with:
                a, b = pair_key(name, other)
                push_current_entry(a, b)

        for other in shared_with:
            a, b = pair_key(name, other)
            old_overlap = pair_overlap.get((a, b), 0)
            pair_overlap[(a, b)] = old_overlap + 1
            neighbors[name].add(other)
            neighbors[other].add(name)
            if pair_overlap[(a, b)] > max_overlap:
                max_overlap = pair_overlap[(a, b)]
            push_current_entry(a, b)

        item_lists[item].add(name)
        answers.append(current_best())

    return answers

Time complexity: Amortized O((s + d) log H) per distinct update, where s is the number of other lists already containing the updated item, d is the number of current positive-overlap neighbors of the updated list, and H is the number of heap entries currently stored. Duplicate updates are O(1) amortized plus lazy-heap cleanup during queries.. Space complexity: O(M + P + R), where M is the number of distinct (list, item) memberships seen so far, P is the number of pairs with positive overlap, and R is the number of lazy heap entries pushed over time..

Hints

1. An update only changes overlap counts for lists that already had the same item, and it only changes Jaccard values for positive-overlap neighbors of the updated list.
2. Use lazy heap entries: push new scores when something changes, and discard stale entries when they reach the top.