0511MediumArrayHash TableBreadth-First SearchGraph TheorySorting

Book Club Reading Ring

Tracked in this browser only

Trains the technique from

LeetCode 1311Get Watched Videos by Your Friends

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A reading club has n members numbered from 0. readBooks[i] lists the titles member i has logged, and a member who logged the same title twice has it listed twice. contacts[i] lists the members that member i swaps books with directly; the relation runs both ways, so if j appears in contacts[i] then i appears in contacts[j].

The rank of a member is the fewest direct swaps needed to pass a book from member member to them, so member has rank 0 and each direct contact of member has rank 1.

Collect every logged entry of every member of rank exactly level, counting each entry separately, so a title logged twice by one member and once by another has been logged three times in that rank. Return the distinct titles from that collection, ordered by how many times they were logged from fewest to most, with titles that were logged the same number of times ordered alphabetically. Return an empty list when no member has that rank.

Examples

Example 1

Input: readBooks = [["reef"], ["kiln", "reef"], ["kiln"], ["moss"]], contacts = [[1, 2], [0], [0], []], member = 0, level = 1
Output: ["reef", "kiln"]

Members 1 and 2 have rank 1. Their logs hold kiln twice and reef once, so reef comes first with one logging and kiln second with two.

Example 2

Input: readBooks = [["one", "two"], ["two", "three"], ["three", "one"], ["four"]], contacts = [[1, 2, 3], [0], [0], [0]], member = 0, level = 1
Output: ["four", "one", "two", "three"]

Members 1, 2 and 3 have rank 1. Between them three was logged twice, while four, one and two were each logged once, so those three come first in alphabetical order and three comes last.

Example 3

Input: readBooks = [["reef"], ["kiln", "reef"], ["kiln"], ["moss"]], contacts = [[1, 2], [0], [0], []], member = 0, level = 2
Output: []

Members 1 and 2 are the only contacts of member 0, and member 3 has no contacts at all, so no member has rank 2 and nothing is collected.

Constraints

n == readBooks.length == contacts.length
2 <= n <= 100
1 <= readBooks[i].length <= 100
1 <= readBooks[i][j].length <= 8
readBooks[i][j] consists of lowercase English letters.
0 <= contacts[i].length < n
0 <= contacts[i][j] < n
contacts[i] never contains i and never repeats a member.
If contacts[i] contains j, then contacts[j] contains i.
0 <= member < n
1 <= level < n

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def titles_at_distance(readBooks: list[list[str]], contacts: list[list[int]], member: int, level: int) -> list[str]:

Java

public List<String> titlesAtDistance(List<List<String>> readBooks, int[][] contacts, int member, int level)

The intended approach

Time O(n + e + t log t) for n members, e links and t distinct titles in the rank.Space O(n + t): the reached flags, the frontier and the tally.

Expand outward from `member` one ring at a time, marking members as reached so nobody lands in two rings; after `level` expansions the frontier is exactly the members of that rank. Tally every logged entry of those members in a dictionary, then order the distinct titles by tally with the title itself as the tie-break.

Pythonentry point: titles_at_distance

def titles_at_distance(readBooks, contacts, member, level):
    # Peel the club off in rings. Ring 0 is the member alone, and each further ring
    # is every unvisited contact of the previous ring, so after level rounds the
    # frontier holds exactly the members whose shortest chain of contacts has that
    # length. Tally the titles of the frontier and order them by tally, then by
    # title.
    # O(n + e + t log t) time, O(n + t) space for n members, e links and t titles.
    total = len(readBooks)
    reached = [False] * total
    reached[member] = True
    frontier = [member]
    for _ in range(level):
        nxt = []
        for u in frontier:
            for v in contacts[u]:
                if not reached[v]:
                    reached[v] = True
                    nxt.append(v)
        frontier = nxt
    tally = {}
    for u in frontier:
        for title in readBooks[u]:
            tally[title] = tally.get(title, 0) + 1
    return sorted(tally, key=lambda title: (tally[title], title))

The obvious version

Relax every link n times to settle the rank of every member, which needs no ordered traversal, then tally the logged entries of the members whose rank matches and pull the titles out one at a time by repeatedly picking the smallest remaining pair. O(n * e + t^2).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_titles_at_distance(readBooks, contacts, member, level):
    total = len(readBooks)
    INF = float("inf")
    dist = [INF] * total
    dist[member] = 0
    for _ in range(total):
        for u in range(total):
            if dist[u] == INF:
                continue
            for v in contacts[u]:
                if dist[u] + 1 < dist[v]:
                    dist[v] = dist[u] + 1
    tally = {}
    for i in range(total):
        if dist[i] == level:
            for title in readBooks[i]:
                tally[title] = tally.get(title, 0) + 1
    items = list(tally.items())
    ordered = []
    while items:
        pick = 0
        for idx in range(1, len(items)):
            if (items[idx][1], items[idx][0]) < (items[pick][1], items[pick][0]):
                pick = idx
        ordered.append(items.pop(pick)[0])
    return ordered

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in