0180MediumArrayHash TableStringDepth-First SearchBreadth-First SearchUnion-FindSorting

Merge Crew Badge Records

Tracked in this browser only

Trains the technique from

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.

Every gate at a depot keeps its own badge log, so one crew member can show up in several logs. You are handed records, where records[i] starts with the crew member's display name and continues with the badge codes that were scanned under that name at one gate.

Badge codes identify a person: if two records list a code in common, they were written by the same crew member. Follow that through as far as it goes, so records linked by a chain of shared codes are all the same person even when no single code is in all of them. One crew member always signs with one display name, though it is quite possible for two unrelated crew members to sign with the very same one, so the display name on its own tells you nothing.

Return one entry per crew member: the display name, followed by that person's badge codes with duplicates removed and sorted in increasing lexicographic order. The entries themselves may come back in any order.

Examples

Example 1

Input: records = [["Nadia", "kx7", "qp2"], ["Omar", "zz1"], ["Nadia", "qp2", "tt9"], ["Nadia", "aa0"]]
Output: [["Nadia", "kx7", "qp2", "tt9"], ["Omar", "zz1"], ["Nadia", "aa0"]]

The first and third records share qp2, so they came from one crew member. The fourth shares nothing with them and belongs to a different crew member who happens to sign the same way.

Example 2

Input: records = [["Sam", "p1", "p2"], ["Sam", "p3", "p4"], ["Sam", "p2", "p3"]]
Output: [["Sam", "p1", "p2", "p3", "p4"]]

The first two records look unrelated until the third links p2 to p3, which pulls all three into one crew member.

Example 3

Input: records = [["Ivy", "zz9", "aa1"]]
Output: [["Ivy", "aa1", "zz9"]]

A single record still has to come back with its codes in increasing order.

Constraints

1 <= records.length <= 1000
2 <= records[i].length <= 10
1 <= records[i][j].length <= 30
records[i][0] consists of English letters.
records[i][j] for j > 0 consists of lowercase English letters and digits.

The values you return may be in any order.

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 merge_badge_records(records: list[list[str]]) -> list[list[str]]:

Java

public List<List<String>> mergeBadgeRecords(List<List<String>> records)

The intended approach

Time O(t * a(t) + t log t) where t is the total number of badge codesSpace O(t)

Treat each record as a node and use a disjoint-set forest over record positions. Keep a map from badge code to the first record that used it; every repeat of that code unions the two records, which makes chains collapse automatically. Finally gather the codes of each set into a set, sort them, and prefix the display name of any record in the set.

Pythonentry point: merge_badge_records

def merge_badge_records(records):
    # Union-find over record positions. Each badge code remembers the first
    # record that used it and links every later record that repeats it, which
    # gives transitivity for free.
    # Time O(t * a(t) + t log t) for t codes in total, dominated by the final
    # per-owner sort. Space O(t) for the code owners and the collected sets.
    parent = list(range(len(records)))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    owner = {}
    for i, record in enumerate(records):
        for code in record[1:]:
            if code in owner:
                a, b = find(owner[code]), find(i)
                if a != b:
                    parent[b] = a
            else:
                owner[code] = i

    collected = {}
    for i, record in enumerate(records):
        collected.setdefault(find(i), set()).update(record[1:])
    return [[records[root][0]] + sorted(codes)
            for root, codes in collected.items()]

The obvious version

Start with one group per record and repeatedly scan every pair of groups, folding two together the moment they share a code. Restart the scan after each fold and stop when a full scan changes nothing.

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_merge_badge_records(records):
    groups = [[record[0], set(record[1:])] for record in records]
    changed = True
    while changed:
        changed = False
        for i in range(len(groups)):
            for j in range(i + 1, len(groups)):
                if groups[i][1] & groups[j][1]:
                    groups[i][1] |= groups[j][1]
                    groups.pop(j)
                    changed = True
                    break
            if changed:
                break
    return [[name] + sorted(codes) for name, codes in groups]

How this problem was checked

Reference solution executed against 11 test cases — 11 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