Constraints

• 0 <= N <= 100000, where N is the number of employees
• Employee IDs are unique integers
• The total number of interest strings across all employees is at most 200000
• Each interest string has length between 1 and 50
• Duplicate interests within the same employee should be treated as one interest

Examples

Solution

def solution(employees):
    interest_to_ids = {}

    for emp_id, interests in employees:
        for interest in set(interests):
            if interest not in interest_to_ids:
                interest_to_ids[interest] = []
            interest_to_ids[interest].append(emp_id)

    result = {}
    for interest in sorted(interest_to_ids):
        result[interest] = sorted(interest_to_ids[interest])

    return result

Time complexity: O(T + sum(m_i log m_i) + U log U), where T is the total number of input interest strings, m_i is the number of employees for interest i, and U is the number of unique interests.. Space complexity: O(T), excluding the input; this stores the inverted index and output..

Hints

1. Think about reversing the relationship: instead of employee -> interests, build interest -> employees.
2. If an employee's list may contain duplicates, convert it to a set before adding the employee ID to each interest bucket.

Constraints

• 0 <= N <= 5000, where N is the number of employees
• Employee IDs are unique integers
• The total number of interest strings across all employees is at most 20000
• Duplicate interests within the same employee should be treated as one interest
• The total number of generated candidate pairs across all interests is at most 200000

Examples

Solution

def solution(employees):
    interest_to_ids = {}

    for emp_id, interests in employees:
        for interest in set(interests):
            if interest not in interest_to_ids:
                interest_to_ids[interest] = set()
            interest_to_ids[interest].add(emp_id)

    pairs = set()

    for ids in interest_to_ids.values():
        sorted_ids = sorted(ids)
        for i in range(len(sorted_ids)):
            for j in range(i + 1, len(sorted_ids)):
                pairs.add((sorted_ids[i], sorted_ids[j]))

    return sorted(pairs)

Time complexity: O(T + sum(k_i log k_i + C(k_i, 2)) + P log P), where T is the total number of input interest strings, k_i is the number of employees with interest i, and P is the number of unique output pairs.. Space complexity: O(T + P), excluding the input; this stores the interest groups and the unique output pairs..

Hints

1. First group employees by interest, then generate employee pairs inside each interest group.
2. Use a set of pairs so that if two employees share multiple interests, the pair is still returned only once.