Constraints

• 1 <= K <= 10^3
• 1 <= M <= K
• Each user's history length is at least K
• Duplicates inside the last K movies count only once because overlap is computed on sets
• All user IDs in one input are of the same comparable type (for example, all strings or all integers)
• Movie IDs are hashable values

Examples

Solution

def solution(K, M, histories):
    from collections import defaultdict

    if len(histories) < 2:
        return []

    users = sorted(histories.keys())
    movie_to_users = defaultdict(list)

    for user in users:
        recent_movies = set(histories[user][-K:])
        for movie in recent_movies:
            movie_to_users[movie].append(user)

    pair_counts = defaultdict(int)

    for users_with_movie in movie_to_users.values():
        n = len(users_with_movie)
        for i in range(n):
            u1 = users_with_movie[i]
            for j in range(i + 1, n):
                u2 = users_with_movie[j]
                pair_counts[(u1, u2)] += 1

    result = [pair for pair, count in pair_counts.items() if count >= M]
    result.sort()
    return result

Time complexity: O(U*K + sum over movies of c_m^2 + R log R), where U is the number of users, c_m is the number of users whose last-K set contains movie m, and R is the number of returned pairs. Space complexity: O(U*K + P), where P is the number of user pairs that share at least one movie.

Hints

1. First reduce each user's last K movies to a set so duplicates do not increase the overlap count.
2. Instead of comparing every pair of users directly, build an inverted index from movie ID to the users whose last-K set contains that movie.