Watch 7 video solutions for People Whose List of Favorite Companies Is Not a Subset of Another List, a medium level problem involving Array, Hash Table, String. This walkthrough by code Explainer has 1,072 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the array favoriteCompanies where favoriteCompanies[i] is the list of favorites companies for the ith person (indexed from 0).
Return the indices of people whose list of favorite companies is not a subset of any other list of favorites companies. You must return the indices in increasing order.
Example 1:
Input: favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]] Output: [0,1,4] Explanation: Person with index=2 has favoriteCompanies[2]=["google","facebook"] which is a subset of favoriteCompanies[0]=["leetcode","google","facebook"] corresponding to the person with index 0. Person with index=3 has favoriteCompanies[3]=["google"] which is a subset of favoriteCompanies[0]=["leetcode","google","facebook"] and favoriteCompanies[1]=["google","microsoft"]. Other lists of favorite companies are not a subset of another list, therefore, the answer is [0,1,4].
Example 2:
Input: favoriteCompanies = [["leetcode","google","facebook"],["leetcode","amazon"],["facebook","google"]] Output: [0,1] Explanation: In this case favoriteCompanies[2]=["facebook","google"] is a subset of favoriteCompanies[0]=["leetcode","google","facebook"], therefore, the answer is [0,1].
Example 3:
Input: favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]] Output: [0,1,2,3]
Constraints:
1 <= favoriteCompanies.length <= 1001 <= favoriteCompanies[i].length <= 5001 <= favoriteCompanies[i][j].length <= 20favoriteCompanies[i] are distinct.favoriteCompanies[i] != favoriteCompanies[j].Problem Overview: You receive a list where favoriteCompanies[i] contains the companies liked by the i-th person. The task is to return the indices of people whose list is not a subset of any other person's list. In other words, if every company in person A's list also appears in person B's list, then A should be excluded.
Approach 1: Brute Force Comparison (O(n2 * k) time, O(k) space)
Compare every person's company list with every other person's list. For each pair (i, j), check whether all companies in favoriteCompanies[i] exist in favoriteCompanies[j]. Converting the second list to a hash set makes membership checks O(1). If every company in i exists in j, then i is a subset and should be excluded from the result. This method directly implements the definition of subset using nested iteration and works reliably for moderate input sizes.
The key operation is repeated membership testing. Without hashing, checking membership would require scanning strings in the list each time, leading to much slower comparisons. Using a set ensures each lookup runs in constant time while iterating through company names. This approach is conceptually simple and demonstrates clear understanding of subset logic using arrays and strings.
Approach 2: Optimized Subset Checking with Early Termination (O(n2 * k) time, O(n * k) space)
First convert every person's company list into a HashSet. This preprocessing allows fast subset checks later. Then iterate over all pairs of people. When checking if set A is a subset of set B, immediately stop once a company from A is missing in B. Early termination significantly reduces comparisons when lists differ early.
Another small optimization is skipping comparisons where A is larger than B. A larger set cannot be a subset of a smaller one. This reduces unnecessary checks and improves average performance while maintaining the same worst‑case complexity. The approach relies heavily on efficient membership operations provided by hash tables.
Recommended for interviews: The optimized hash‑set subset comparison is typically expected. Interviewers want to see you translate the subset condition into efficient set operations. Starting with the brute force explanation shows clear reasoning, but switching to hashed sets and early termination demonstrates stronger algorithmic thinking and practical optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Comparison | O(n^2 * k) | O(k) | Simple baseline solution; good for understanding subset relationships |
| Hash Set Subset Check | O(n^2 * k) | O(n * k) | General case with faster membership checks using hash tables |
| Optimized with Early Termination | O(n^2 * k) worst case | O(n * k) | Preferred in interviews; skips unnecessary comparisons and stops early when mismatch appears |