Find user pairs with overlapping last K movies

You are given the same user movie-watching histories as in the previous problem. Each user’s history is an ordered list of movie IDs from earliest to latest.

Assume:

• histories is a dictionary/map from user_id to a list of movie_id .
• Each list has at least K movies.

Task Given integers K and M (1 ≤ M ≤ K), find all unordered pairs of distinct users (u1, u2) such that:

• If L(u) is the list of the last K movies in user u 's history, then the number of common movies between L(u1) and L(u2) (treated as sets or as lists ignoring order and duplicates) is at least M .

Formally, define:

• S(u) = set of the last K movies in user u's history .
• Return all pairs (u1, u2) with u1 < u2 (or any consistent ordering) such that |S(u1) ∩ S(u2)| ≥ M .

Input

• An integer K (1 ≤ K ≤ 10^3).
• An integer M (1 ≤ M ≤ K).
• A map/dictionary histories: user_id → [movie_id1, movie_id2, ..., movie_idN] where N ≥ K for each user.

Output

• A list of all user pairs (u1, u2) that satisfy |S(u1) ∩ S(u2)| ≥ M .

Example Let K = 4, M = 2 and:

• user A: [m1, m2, m3, m4, m5]
• user B: [m2, m3, m6, m4]
• user C: [m7, m8, m9, m10]

Then:

• S(A) = {m2, m3, m4, m5}
• S(B) = {m2, m3, m4, m6}
• S(C) = {m7, m8, m9, m10}

We have:

• |S(A) ∩ S(B)| = 3 ≥ M → (A, B) is a valid pair.
• |S(A) ∩ S(C)| = 0 < M → invalid.
• |S(B) ∩ S(C)| = 0 < M → invalid.

So the output should include the pair (A, B) only.

Design an efficient algorithm for large numbers of users and movies, and analyze its time and space complexity.