Largest Related Product Cluster
In product catalog management, understanding relationships between items is crucial for recommendations, marketing, and inventory optimization. Products are often categorized by various tags. We define two products as 'related' if they share at least one common tag. This relationship extends transitively: if Product A is related to Product B, and Product B is related to Product C, then A, B, and C all belong to the same 'related product cluster'. Your task is to identify the largest such cluster in a given catalog.
Implement the function findLargestRelatedCluster that takes a list of products, where each product is represented by a list of strings (its tags). The function should return the size of the largest group of products that are transitively related.
items: string[][]
items is a list where each inner string[] represents a product's tags. items[i] contains the tags associated with the i-th product.number
items list: If the input items list is empty, return 0.["tech", "tech"]). These duplicates should be treated as a single unique tag for the purpose of establishing relationships.items is not empty).Examples
Example 1
Input:
items = [["electronics", "gadget"], ["gadget", "smart_home"], ["clothing"], ["electronics"]]
Output:
3
Note:
Product 0 (electronics, gadget) is related to Product 1 (gadget, smart_home) via 'gadget'. Product 0 is also related to Product 3 (electronics) via 'electronics'. Thus, Products 0, 1, and 3 form one cluster of size 3. Product 2 (clothing) forms a separate cluster of size 1. The largest cluster has size 3.
Example 2
Input:
items = [["apple"], ["banana"], ["orange"]]
Output:
1
Note:
No two products share any tags. Each product forms a cluster of size 1. The largest cluster size is 1.
Example 3
Input:
items = [["A", "B"], ["C", "D"], ["B", "E"], ["F"], ["D", "G"]]
Output:
2
Note:
Product 0 (A, B) and Product 2 (B, E) share 'B', forming a cluster {0, 2} of size 2. Product 1 (C, D) and Product 4 (D, G) share 'D', forming a cluster {1, 4} of size 2. Product 3 (F) forms a cluster {3} of size 1. The largest cluster has size 2.
Example 4
Input:
items = []
Output:
0
Note:
No products are provided, so the largest cluster size is 0.
Constraints
0 <= items.length <= 10^4 (number of products, N)0 <= items[i].length <= 100 (number of tags per product, K)1 <= tag.length <= 50 (length of each tag string)10^5 (M).Loading editor...