Diverse Product Bundle Recommendation
Nykaa aims to enhance customer experience by offering intelligent product bundle recommendations. A key challenge is ensuring these bundles are diverse, exposing customers to a wider range of products and categories. This problem asks you to determine if a specific product can be part of a "diverse bundle" – a set of compatible products that collectively span at least a minimum number of distinct product categories. This capability is crucial for generating engaging and comprehensive recommendations.
Implement a function canFormDiverseBundle that determines if a given startProductId can be included in a bundle of compatible products such that the bundle contains at least minCategories distinct product categories. A "bundle" in this context is defined as a connected component in the compatibility graph that includes startProductId.
Your function will receive the following parameters:
numProducts: An integer representing the total number of products, indexed from 0 to numProducts - 1.compatibilities: A 2D array of integers, where each inner array [u, v] denotes that product u and product v are compatible. Compatibility is bidirectional.productCategories: An array of integers where productCategories[i] is the category ID for product i. Category IDs are positive integers.startProductId: An integer representing the ID of the product from which to start forming the bundle.minCategories: An integer representing the minimum number of distinct product categories required in the bundle.The function should return a boolean: true if startProductId can be part of such a diverse bundle, false otherwise.
0 to numProducts - 1.u is compatible with v, then v is compatible with u.startProductId and all other products reachable from it through compatibility links.startProductId has no compatibilities, the bundle consists only of startProductId itself.minCategories will always be at least 1.Examples
Example 1
Input:
numProducts = 5, compatibilities = [[0, 1], [1, 2], [2, 3], [3, 4]], productCategories = [100, 200, 100, 300, 200], startProductId = 0, minCategories = 3
Output:
true
Note:
Starting from product 0 (Category 100), we can reach product 1 (Category 200), product 2 (Category 100), product 3 (Category 300), and product 4 (Category 200). The distinct categories encountered are {100, 200, 300}, which is 3 distinct categories. Since 3 >= minCategories (3), the function returns true.
Example 2
Input:
numProducts = 3, compatibilities = [[0, 1], [1, 2]], productCategories = [100, 200, 100], startProductId = 0, minCategories = 3
Output:
false
Note:
Starting from product 0 (Category 100), we can reach product 1 (Category 200) and product 2 (Category 100). The distinct categories encountered are {100, 200}, which is 2 distinct categories. Since 2 < minCategories (3), the function returns false.
Example 3
Input:
numProducts = 3, compatibilities = [[1, 2]], productCategories = [100, 200, 300], startProductId = 0, minCategories = 2
Output:
false
Note:
Product 0 is not compatible with any other product. The bundle consists only of product 0 (Category 100). The distinct categories are {100}, which is 1 distinct category. Since 1 < minCategories (2), the function returns false.
Example 4
Input:
numProducts = 2, compatibilities = [[0, 1]], productCategories = [100, 200], startProductId = 0, minCategories = 1
Output:
true
Note:
Starting from product 0 (Category 100), we immediately have 1 distinct category. Since 1 >= minCategories (1), the function returns true.
Constraints
1 <= numProducts <= 10^50 <= compatibilities.length <= 10^5compatibilities[i].length == 20 <= u, v < numProducts for all [u, v] in compatibilities1 <= productCategories[i] <= 10^9 for all i0 <= startProductId < numProducts1 <= minCategories <= numProductscompatibilities may contain self-loops or multiple edges between the same pair of products. Treat them as a single edge for reachability.startProductId. Assume valid inputs.minCategories = 1, or sparse compatibility graphs.Loading editor...