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.
This approach involves comparing each person's list of favorite companies with every other person's list to check if one is a subset of the other. By iterating through each pair of lists, we determine the subset relationships.
We then collect the indices of those lists which are not subsets of any other list.
This C program defines a helper function isSubset to determine if one list of favorite companies is a subset of another. It then iterates over all possible pairs of lists and utilizes this helper function to check their subset relationship.
The main function, peopleNotSubset, builds a list of all indices whose favorite companies are not a subset of any other's favorite companies, returning that list.
Time Complexity: O(n^2 * m), where n is the number of lists and m is the average number of companies in each list. This comes from comparing each list to every other list.
Space Complexity: O(n), needed for storing the result indices.
An optimized approach is to sort the lists based on their lengths and check smaller lists against larger ones first. By doing this, we can potentially terminate the checking early if a subset relationship is found quicker.
Only necessary comparisons are made, possibly reducing the average number of checks.
This C approach first sorts the indices of the favorite companies based on the list lengths. By processing shorter lists first, it ensures that any potential subsets are identified rapidly without unnecessary comparisons, optimizing the runtime.
C
Time Complexity: O(n^2 * m) due to sorting and comparison calls, but usually performs faster compared to naive approach due to short-circuit conditions.
Space Complexity: O(n) for indices and result storage arrays.
We can map each company to a unique integer. Then, for each person, we convert their favorite companies into a set of integers. Finally, we check if the favorite companies of one person are a subset of another person's favorite companies.
The time complexity is (n times m times k + n^2 times m), and the space complexity is O(n times m). Here, n and m are the lengths of favoriteCompanies and the average length of each company's list, respectively, and k is the average length of each company.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Comparison | Time Complexity: O(n^2 * m), where n is the number of lists and m is the average number of companies in each list. This comes from comparing each list to every other list. Space Complexity: O(n), needed for storing the result indices. |
| Optimized Subset Checking with Early Termination | Time Complexity: O(n^2 * m) due to sorting and comparison calls, but usually performs faster compared to naive approach due to short-circuit conditions. Space Complexity: O(n) for indices and result storage arrays. |
| Hash Table | — |
| 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 |
1452 People Whose List of Favorite Companies Is Not a Subset of Another List || Weekly Contest 189 • code Explainer • 1,072 views views
Watch 6 more video solutions →Practice People Whose List of Favorite Companies Is Not a Subset of Another List with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor