Largest Item Association Group
Filed under Amazon
Free read 3 of 3Check if inputs are given as list of pairs, and whether items are always strings.
The question
Given pairs of associated items, find the largest group of associated items. If groups are equal in size, return the one that is lexicographically smallest.
Constraints
- Item names are strings
- Associations are bidirectional and transitive
Examples
- Input
- assoc = [['item1', 'item2'], ['item3', 'item4'], ['item1', 'item4']]
- Output
- ['item1', 'item2', 'item3', 'item4']
- Why
- All items form a single connected component of size 4.
Approach
Check if inputs are given as list of pairs, and whether items are always strings.
Build an adjacency list and run DFS/BFS from every unvisited node to discover components.
Use Disjoint Set Union (DSU) with path compression and union by rank to group elements efficiently, then aggregate and find the target group.
Empty association list, or all items in separate isolated pairs of equal size.
Tips
- What they are testing: Test disconnected components and ties in group sizes requiring alphabetical tie-breaking.
- Common mistake: Failing to normalize root representatives or missing lexicographical sorting on the resulting groups.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.