Group users by same last K watched movies

You are given a list of users' movie-watching histories. Each user’s history is an ordered list of movie IDs in the order they were watched (earliest to latest).

Assume:

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

Task Write an algorithm to group users such that, within each group, all users share the exact same set of the last K movies they watched (ignoring order within those last K movies). Two users belong to the same group if the following holds:

• Let S(u) be the set of the last K movies in user u 's history.
• Users u1 and u2 are in the same group if S(u1) = S(u2) .

Input

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

Output

• Return a list of groups, where each group is a list of user_id s. Only groups of size ≥ 2 (i.e., at least two users with the same last-K set) need to be returned.

Example Suppose K = 3 and:

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

Then:

• Last 3 for A: {m3, m4, m5}
• Last 3 for B: {m3, m4, m5}
• Last 3 for C: {m3, m4, m6}

The output should group A and B together, and C can be omitted or appear alone depending on your choice, but only multi-user groups are required in the output.

Describe the algorithm and its time and space complexity.