Frontend School

Largest Related Product Cluster

DSA
medium

Largest Related Product Cluster

Medium
Union Find
Graph
Data Structures

Overview

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.

What you need to do / Task

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.

Input & output

  • Input: 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.
  • Output: number
    • The size of the largest cluster of related products. If no products are provided, return 0.

Clarifications

  • Empty items list: If the input items list is empty, return 0.
  • Empty tag list for a product: A product might have an empty list of tags. Such a product cannot be related to any other product, unless it's explicitly part of a group through other means (which it won't be if it has no tags).
  • Duplicate tags: A product might have duplicate tags within its own list (e.g., ["tech", "tech"]). These duplicates should be treated as a single unique tag for the purpose of establishing relationships.
  • No common tags: If no two products share any tags, each product forms a cluster of size 1. In this case, the largest cluster size would be 1 (assuming items is not empty).

Examples

1

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.

2

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.

3

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.

4

Example 4

Input:

items = []

Output:

0

Note:

No products are provided, so the largest cluster size is 0.

Constraints

Constraints & assumptions

  • 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)
  • All tag strings consist of lowercase English letters and underscores.
  • The total number of unique tags across all products is at most 10^5 (M).

Out of scope

  • Performance optimization beyond typical Union-Find techniques (e.g., highly specialized string hashing, concurrent processing).
  • Handling non-string tags or tags with special characters outside of the specified constraint.

What interviewers evaluate

  • Correctness: The solution correctly identifies and counts products within transitively related clusters.
  • Algorithm Choice: Appropriate use of the Union-Find data structure to efficiently manage product relationships.
  • Time and Space Complexity: An efficient solution that meets the given constraints, demonstrating understanding of Union-Find's amortized complexity.
  • Code Quality: Clean, readable, and well-structured code with appropriate variable names and comments where necessary.

Loading editor...