People Whose List of Favorite Companies Is Not a Subset of Another List solution and explanation
Google
6 more videos on this problem
1452 People Whose List of Favorite Companies Is Not a Subset of Another List || Weekly Contest 189code Explainer · 6:38 · 1K views
1452. People Whose List of Favorite Companies Is Not a Subset of Another List (Leetcode Medium)Programming Live with Larry · 7:00 · 760 views
People Whose List of Favorite Companies Is Not a Subset of Another List (Leetcode 1452)Coding Interviews · 24:17 · 443 views
【每日一题】1452. People Whose List of Favorite Companies Is Not a Subset of Another List, 11/20/2020Huifeng Guan · 25:20 · 296 views
Leetcode 1452 People Whose List of Favorite Companies Is Not a Subset of Another ListMaxMing · 2:52 · 246 views
Leetcode 1452. People Whose List of Favorite Companies Is Not a Subset of Another List (set)LetsCode · 7:00 · 170 views
LeetCode 1452: People Whose List of Favorite Companies Is Not a Subset of Another ListAlitaCode · 30:03 · 16 views
The problem
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 <= 20- All strings in
favoriteCompanies[i]are distinct. - All lists of favorite companies are distinct, that is, If we sort alphabetically each list then
favoriteCompanies[i] != favoriteCompanies[j]. - All strings consist of lowercase English letters only.
Approach overview
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 1: Brute Force Comparison
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.
def people_not_subset(favorite_companies):
n = len(favorite_companies)
result = []
for i in range(n):
is_subset = False
for j in range(n):
if i != j and set(favorite_companies[i]).issubset(favorite_companies[j]):
is_subset = True
break
if not is_subset:
result.append(i)
return result
# Example usage:
favorite_companies = [
["leetcode", "google", "facebook"],
["google", "microsoft"],
["google", "facebook"],
["google"],
["amazon"]
]
output = people_not_subset(favorite_companies)
print(output)import java.util.*;
public class FavoriteCompanies {
public static List<Integer> peopleNotSubset(List<List<String>> favoriteCompanies) {
int n = favoriteCompanies.size();
List<Integer> result = new ArrayList<>();
boolean[] isSubset = new boolean[n];
for (int i = 0; i < n; i++) {
if (isSubset[i]) continue;
for (int j = 0; j < n; j++) {
if (i != j && favoriteCompanies.get(i).size() <= favoriteCompanies.get(j).size()) {
Set<String> set = new HashSet<>(favoriteCompanies.get(j));
if (set.containsAll(favoriteCompanies.get(i))) {
isSubset[i] = true;
break;
}
}
}
if (!isSubset[i]) result.add(i);
}
return result;
}
public static void main(String[] args) {
List<List<String>> favoriteCompanies = Arrays.asList(
Arrays.asList("leetcode", "google", "facebook"),
Arrays.asList("google", "microsoft"),
Arrays.asList("google", "facebook"),
Arrays.asList("google"),
Arrays.asList("amazon")
);
List<Integer> result = peopleNotSubset(favoriteCompanies);
System.out.println(result);
}
}#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
bool isSubset(const vector<string>& a, const vector<string>& b) {
unordered_set<string> setA(a.begin(), a.end());
for (const string& company : b) {
if (setA.find(company) != setA.end()) {
setA.erase(company);
}
}
return setA.empty();
}
vector<int> peopleNotSubset(vector<vector<string>>& favoriteCompanies) {
vector<int> result;
int n = favoriteCompanies.size();
for (int i = 0; i < n; ++i) {
bool subset = false;
for (int j = 0; j < n; ++j) {
if (i != j && favoriteCompanies[i].size() <= favoriteCompanies[j].size() && isSubset(favoriteCompanies[i], favoriteCompanies[j])) {
subset = true;
break;
}
}
if (!subset) {
result.push_back(i);
}
}
return result;
}
int main() {
vector<vector<string>> favoriteCompanies = {
{"leetcode", "google", "facebook"},
{"google", "microsoft"},
{"google", "facebook"},
{"google"},
{"amazon"}
};
vector<int> result = peopleNotSubset(favoriteCompanies);
for (int index : result) {
cout << index << " ";
}
cout << endl;
return 0;
}function peopleNotSubset(favoriteCompanies) {
let result = [];
const n = favoriteCompanies.length;
for (let i = 0; i < n; i++) {
let isSubset = false;
for (let j = 0; j < n; j++) {
if (i !== j && favoriteCompanies[i].every(company => favoriteCompanies[j].includes(company))) {
isSubset = true;
break;
}
}
if (!isSubset) {
result.push(i);
}
}
return result;
}
// Example usage
const favoriteCompanies = [
["leetcode", "google", "facebook"],
["google", "microsoft"],
["google", "facebook"],
["google"],
["amazon"]
];
console.log(peopleNotSubset(favoriteCompanies));#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
bool isSubset(char **list1, int len1, char **list2, int len2) {
int count = 0;
for (int i = 0; i < len1; ++i) {
for (int j = 0; j < len2; ++j) {
if (strcmp(list1[i], list2[j]) == 0) {
count++;
break;
}
}
}
return count == len1;
}
int* peopleNotSubset(char ***favoriteCompanies, int favoriteCompaniesSize, int** cols, int* returnSize) {
int *result = (int*)malloc(favoriteCompaniesSize * sizeof(int));
int resultIndex = 0;
for (int i = 0; i < favoriteCompaniesSize; ++i) {
bool isSubsetOfOthers = false;
for (int j = 0; j < favoriteCompaniesSize; ++j) {
if (i != j && isSubset(favoriteCompanies[i], cols[i][0], favoriteCompanies[j], cols[j][0])) {
isSubsetOfOthers = true;
break;
}
}
if (!isSubsetOfOthers) {
result[resultIndex++] = i;
}
}
*returnSize = resultIndex;
return result;
}
int main() {
/* Example usage */
char *favoriteCompanies1[] = {"leetcode", "google", "facebook"};
char *favoriteCompanies2[] = {"google", "microsoft"};
char *favoriteCompanies3[] = {"google", "facebook"};
char *favoriteCompanies4[] = {"google"};
char *favoriteCompanies5[] = {"amazon"};
char **favoriteCompaniesArray[] = { favoriteCompanies1, favoriteCompanies2, favoriteCompanies3, favoriteCompanies4, favoriteCompanies5 };
int cols[] = {3, 2, 2, 1, 1};
int *colsArray[] = { &cols[0], &cols[1], &cols[2], &cols[3], &cols[4] };
int returnSize = 0;
int *result = peopleNotSubset(favoriteCompaniesArray, 5, colsArray, &returnSize);
printf("Output: [");
for (int i = 0; i < returnSize; ++i) {
printf("%d", result[i]);
if (i < returnSize - 1) printf(", ");
}
printf("]\n");
free(result);
return 0;
}using System;
using System.Collections.Generic;
class FavoriteCompanies {
public static IList<int> PeopleNotSubset(IList<IList<string>> favoriteCompanies) {
int n = favoriteCompanies.Count;
var result = new List<int>();
bool[] isSubset = new bool[n];
for (int i = 0; i < n; i++) {
if (isSubset[i]) continue;
for (int j = 0; j < n; j++) {
if (i != j && favoriteCompanies[i].Count <= favoriteCompanies[j].Count) {
var set = new HashSet<string>(favoriteCompanies[j]);
bool subset = true;
foreach (string company in favoriteCompanies[i]) {
if (!set.Contains(company)) {
subset = false;
break;
}
}
if (subset) {
isSubset[i] = true;
break;
}
}
}
if (!isSubset[i]) result.Add(i);
}
return result;
}
static void Main(string[] args) {
IList<IList<string>> favoriteCompanies = new List<IList<string>> {
new List<string> { "leetcode", "google", "facebook" },
new List<string> { "google", "microsoft" },
new List<string> { "google", "facebook" },
new List<string> { "google" },
new List<string> { "amazon" }
};
IList<int> result = PeopleNotSubset(favoriteCompanies);
Console.WriteLine(string.Join(", ", result));
}
}The Python solution utilizes the set operations. It determines if a list is a subset of another directly by converting lists to sets and applying the issubset method. This leads to clear and concise subset checks.
Time Complexity: O(n^2 * m), caused by comparing each pair of company lists.
Space Complexity: O(m), for storing subsets during comparisons.
Approach 2: Optimized Subset Checking with Early Termination
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.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
int compare(const void *a, const void *b, void *arr) {
int idxA = *(int *) a;
int idxB = *(int *) b;
int *columnSizes = (int *)arr;
return columnSizes[idxA] - columnSizes[idxB];
}
bool isSubset(char **list1, int len1, char **list2, int len2) {
int count = 0;
for (int i = 0; i < len1; ++i) {
for (int j = 0; j < len2; ++j) {
if (strcmp(list1[i], list2[j]) == 0) {
count++;
break;
}
}
}
return count == len1;
}
int* peopleNotSubset(char ***favoriteCompanies, int favoriteCompaniesSize, int** cols, int* returnSize) {
int *indices = (int*)malloc(favoriteCompaniesSize * sizeof(int));
for (int i = 0; i < favoriteCompaniesSize; ++i) {
indices[i] = i;
}
qsort_r(indices, favoriteCompaniesSize, sizeof(int), compare, (void *)*cols);
int *result = (int*)malloc(favoriteCompaniesSize * sizeof(int));
int resultIndex = 0;
for (int p = 0; p < favoriteCompaniesSize; ++p) {
int i = indices[p];
bool isSubsetOfOthers = false;
for (int q = 0; q < favoriteCompaniesSize; ++q) {
int j = indices[q];
if (i != j && cols[i][0] <= cols[j][0] && isSubset(favoriteCompanies[i], cols[i][0], favoriteCompanies[j], cols[j][0])) {
isSubsetOfOthers = true;
break;
}
}
if (!isSubsetOfOthers) {
result[resultIndex++] = i;
}
}
*returnSize = resultIndex;
free(indices);
return result;
}
int main() {
/* Example usage */
char *favoriteCompanies1[] = {"leetcode", "google", "facebook"};
char *favoriteCompanies2[] = {"google", "microsoft"};
char *favoriteCompanies3[] = {"google", "facebook"};
char *favoriteCompanies4[] = {"google"};
char *favoriteCompanies5[] = {"amazon"};
char **favoriteCompaniesArray[] = { favoriteCompanies1, favoriteCompanies2, favoriteCompanies3, favoriteCompanies4, favoriteCompanies5 };
int cols[] = {3, 2, 2, 1, 1};
int *colsArray[] = { &cols[0], &cols[1], &cols[2], &cols[3], &cols[4] };
int returnSize = 0;
int *result = peopleNotSubset(favoriteCompaniesArray, 5, colsArray, &returnSize);
printf("Output: [");
for (int i = 0; i < returnSize; ++i) {
printf("%d", result[i]);
if (i < returnSize - 1) printf(", ");
}
printf("]\n");
free(result);
return 0;
}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.
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.
Approach 3: Hash Table
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.
function peopleIndexes(favoriteCompanies: string[][]): number[] {
const n = favoriteCompanies.length;
const d: Map<string, number> = new Map();
let idx = 0;
const nums: Set<number>[] = Array.from({ length: n }, () => new Set<number>());
for (let i = 0; i < n; i++) {
for (const s of favoriteCompanies[i]) {
if (!d.has(s)) {
d.set(s, idx++);
}
nums[i].add(d.get(s)!);
}
}
const check = (a: Set<number>, b: Set<number>): boolean => {
for (const x of a) {
if (!b.has(x)) {
return false;
}
}
return true;
};
const ans: number[] = [];
for (let i = 0; i < n; i++) {
let ok = true;
for (let j = 0; j < n && ok; j++) {
if (i !== j && check(nums[i], nums[j])) {
ok = false;
}
}
if (ok) {
ans.push(i);
}
}
return ans;
}func peopleIndexes(favoriteCompanies [][]string) (ans []int) {
n := len(favoriteCompanies)
d := make(map[string]int)
idx := 0
nums := make([]map[int]struct{}, n)
for i := 0; i < n; i++ {
nums[i] = make(map[int]struct{})
for _, s := range favoriteCompanies[i] {
if _, ok := d[s]; !ok {
d[s] = idx
idx++
}
nums[i][d[s]] = struct{}{}
}
}
check := func(a, b map[int]struct{}) bool {
for x := range a {
if _, ok := b[x]; !ok {
return false
}
}
return true
}
for i := 0; i < n; i++ {
ok := true
for j := 0; j < n && ok; j++ {
if i != j && check(nums[i], nums[j]) {
ok = false
}
}
if ok {
ans = append(ans, i)
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Comparison | Time Complexity: O(n^2 * m), caused by comparing each pair of company lists. Space Complexity: O(m), for storing subsets during comparisons. |
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is People Whose List of Favorite Companies Is Not a Subset of Another List easy or hard?
The problem is rated Medium because the core idea is simple but requires careful implementation. Recognizing the subset relationship and optimizing comparisons with hash sets is the key step that elevates it beyond an easy problem.
People Whose List of Favorite Companies Is Not a Subset of Another List Python/Java solution
In Python, convert each list to a set and use set operations like subset checks or manual iteration with membership tests. In Java, use HashSet<String> for each list and compare sets using contains checks. Both implementations follow the same O(n^2 * k) approach.
How to solve People Whose List of Favorite Companies Is Not a Subset of Another List in O(n)?
An O(n) solution is generally not feasible because each person's list must potentially be compared with many others to verify subset relationships. The practical solution uses pairwise comparisons with hash sets, resulting in O(n^2 * k) complexity.
What is the best approach for People Whose List of Favorite Companies Is Not a Subset of Another List?
The most practical approach converts each person's company list into a hash set and compares it against other sets. For each pair of people, check if one set is a subset of another and terminate early when a missing company is found. This method runs in O(n^2 * k) time with O(n * k) space, where k is the average list length.
Is People Whose List of Favorite Companies Is Not a Subset of Another List asked at Google/Amazon/Meta?
Subset and set‑comparison problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The question tests understanding of hash sets, efficient membership checks, and careful pairwise comparison logic.
What data structure is used in People Whose List of Favorite Companies Is Not a Subset of Another List?
Hash sets are the primary data structure used. Each list of company names is converted into a set so that membership checks run in constant time. Arrays store the original lists, while hash tables enable fast subset verification.
What is the time complexity of People Whose List of Favorite Companies Is Not a Subset of Another List?
The standard solution runs in O(n^2 * k) time. You compare every pair of people (n^2) and check up to k companies when verifying subset relationships. Using hash sets keeps membership checks O(1), making the comparison efficient.