People Whose List of Favorite Companies Is Not a Subset of Another List

Med

#1342Time: O(N^2 * M * L), where N is the number of people, M is the maximum number of companies, and L is the maximum length of a company name. The N^2 factor comes from the nested loops. The M*L factor comes from the `containsAll` operation on sets of strings, which involves hashing and comparing M strings of average length L.Space: O(N * M * L), where N is the number of people, M is the maximum number of companies for a person, and L is the maximum length of a company name. This space is required to store the hash sets of company names.1 company

Data structures

Array Hash Table String

Companies

Datadog

Prompt

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 <= 100
1 <= favoriteCompanies[i].length <= 500
1 <= 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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. We iterate through every pair of people (i, j) and check if the favorite company list of person i is a subset of person j's list. To make the subset check efficient, we convert the lists of companies into Hash Sets, which provide average O(1) time for containment checks.

Algorithm

Initialize an empty list result to store the final indices.
Convert each person's list of favorite companies from a List<String> to a HashSet<String>. This allows for faster lookups when checking for subsets. Store these sets in a new list, say companySets.
Iterate through each person i from 0 to n-1 (where n is the total number of people).
For each person i, assume their list is not a subset of any other. Use a boolean flag, isSubset, initialized to false.
Start a nested loop to compare person i with every other person j.
If i and j are the same, skip the comparison.
A crucial optimization: if the size of i's company set is greater than or equal to the size of j's set, i's list cannot be a proper subset of j's list. Skip the detailed check in this case.
Perform the subset check: companySets.get(j).containsAll(companySets.get(i)). This checks if every company in i's set is present in j's set.
If i's set is a subset of j's set, set isSubset = true and break out of the inner loop (over j), as we've confirmed person i's list is a subset.
After the inner loop completes, if isSubset is still false, it means no other list contains all of person i's favorite companies. Add the index i to the result list.
After iterating through all people, return the result list.

Walkthrough

The core idea is to perform a pairwise comparison among all the lists of favorite companies. For each person's list, we check if it's a subset of any other person's list.

To implement the subset check efficiently, we first convert each List<String> of companies into a HashSet<String>. This data structure is ideal for checking the presence of an element quickly.

The algorithm proceeds as follows:

Create a list of HashSet<String> from the input favoriteCompanies.
Iterate through each person i.
For each i, iterate through all other people j.
If list[i] is a subset of list[j], we mark i as a subset and move to the next person.
If we finish checking all j for a given i and haven't found it to be a subset of any other list, we add i to our result.

1import java.util.*;2 3class Solution {4    public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {5        int n = favoriteCompanies.size();6        List<Set<String>> companySets = new ArrayList<>();7        for (List<String> companies : favoriteCompanies) {8            companySets.add(new HashSet<>(companies));9        }10 11        List<Integer> result = new ArrayList<>();12        for (int i = 0; i < n; i++) {13            boolean isSubset = false;14            for (int j = 0; j < n; j++) {15                if (i == j) {16                    continue;17                }18                // A list can only be a proper subset of a larger list.19                if (companySets.get(i).size() >= companySets.get(j).size()) {20                    continue;21                }22                // Check if set i is a subset of set j23                if (companySets.get(j).containsAll(companySets.get(i))) {24                    isSubset = true;25                    break;26                }27            }28            if (!isSubset) {29                result.add(i);30            }31        }32        return result;33    }34}

Complexity

Time

O(N^2 * M * L), where N is the number of people, M is the maximum number of companies, and L is the maximum length of a company name. The N^2 factor comes from the nested loops. The M*L factor comes from the `containsAll` operation on sets of strings, which involves hashing and comparing M strings of average length L.

Space

O(N * M * L), where N is the number of people, M is the maximum number of companies for a person, and L is the maximum length of a company name. This space is required to store the hash sets of company names.

Trade-offs

Pros

Relatively simple to understand and implement.
Directly follows the logic of the problem description.

Cons

The time complexity is high due to repeated string hashing and comparisons within the nested loops.
It may result in a 'Time Limit Exceeded' (TLE) error on platforms with strict time limits, especially for larger inputs.

The bottleneck in the brute-force approach is the repeated string operations (hashing and comparison) inside the main loops. This optimized approach tackles that by first mapping every unique company string to a unique integer. All subsequent comparisons and subset checks are then performed on sets of integers, which is significantly faster than operating on strings.

Algorithm

Map Strings to Integers:
- Create a HashMap<String, Integer> to map each unique company name to a unique integer ID.
- Iterate through all companies for all people. If a company name is not in the map, assign it a new integer ID and add it to the map.
Create Integer Sets:
- Create a List<Set<Integer>>.
- For each person, create a HashSet<Integer> representing their favorite companies using the integer IDs from the map.
Perform Subset Check:
- Initialize an empty list result.
- Iterate through each person i from 0 to n-1.
- Assume i is not a subset (isSubset = false).
- Iterate through every other person j.
- If the size of i's integer set is greater than or equal to the size of j's set, i cannot be a proper subset, so continue.
- Check if j's integer set contains all elements of i's integer set using setJ.containsAll(setI).
- If it is a subset, set isSubset = true and break the inner loop.
Collect Result:
- If isSubset remains false after checking all j, add i to the result list.
- Return the result list.

Walkthrough

This method improves upon the brute-force approach by reducing the cost of comparisons inside the nested loops.

Integer Mapping: We first perform a pre-processing step. We iterate through all the companies of all people and build a map from each unique company name (a String) to a unique Integer. This ensures that each company is represented by a simple, fast-to-compare integer.
Integer Set Creation: We then create a new list of sets, where each set contains the integer IDs of a person's favorite companies.
Subset Check: With the integer sets, we perform the same pairwise comparison as in the brute-force method. However, the containsAll operation on sets of integers is much faster than on sets of strings, as integer hashing and comparison is a constant time operation.

This pre-computation work pays off by speeding up the most expensive part of the algorithm—the N*N comparisons.

1import java.util.*;2 3class Solution {4    public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {5        // 1. Map strings to integers and create integer sets6        Map<String, Integer> companyToInt = new HashMap<>();7        int nextId = 0;8        List<Set<Integer>> companyIntSets = new ArrayList<>();9 10        for (List<String> companies : favoriteCompanies) {11            Set<Integer> currentSet = new HashSet<>();12            // Sort companies to potentially improve cache performance, though not strictly necessary for correctness13            // Collections.sort(companies);14            for (String company : companies) {15                if (!companyToInt.containsKey(company)) {16                    companyToInt.put(company, nextId++);17                }18                currentSet.add(companyToInt.get(company));19            }20            companyIntSets.add(currentSet);21        }22 23        // 2. Perform subset check on integer sets24        int n = favoriteCompanies.size();25        List<Integer> result = new ArrayList<>();26        for (int i = 0; i < n; i++) {27            boolean isSubset = false;28            for (int j = 0; j < n; j++) {29                if (i == j) {30                    continue;31                }32                Set<Integer> setI = companyIntSets.get(i);33                Set<Integer> setJ = companyIntSets.get(j);34 35                if (setI.size() >= setJ.size()) {36                    continue;37                }38                39                if (setJ.containsAll(setI)) {40                    isSubset = true;41                    break;42                }43            }44            if (!isSubset) {45                result.add(i);46            }47        }48        49        return result;50    }51}

Complexity

Time

O(N*M*L + N^2*M). The first term `N*M*L` is for the initial mapping of strings to integers. The second term `N^2*M` is for the nested loops performing subset checks on integer sets. This is a major improvement over the O(N^2*M*L) of the brute-force approach.

Space

O(N * M * L). The `companyToInt` map can store up to `N * M` unique companies, with the total space for strings being dominant. The integer sets require O(N * M) space.

Trade-offs

Pros

Significantly more efficient and likely to pass within time limits.
Reduces the complexity of the core comparison loop by replacing expensive string operations with cheap integer operations.

Cons

Requires an initial pre-processing step to build the string-to-integer map.
Uses more memory to store both the integer map and the integer sets.

Solutions

Solution

1class Solution { public List < Integer > peopleIndexes ( List < List < String >> favoriteCompanies ) { Map < String , Integer > d = new HashMap <>(); int idx = 0 ; int n = favoriteCompanies . size (); Set < Integer >[] t = new Set [ n ]; for ( int i = 0 ; i < n ; ++ i ) { var v = favoriteCompanies . get ( i ); for ( var c : v ) { if (! d . containsKey ( c )) { d . put ( c , idx ++); } } Set < Integer > s = new HashSet <>(); for ( var c : v ) { s . add ( d . get ( c )); } t [ i ] = s ; } List < Integer > ans = new ArrayList <>(); for ( int i = 0 ; i < n ; ++ i ) { boolean ok = true ; for ( int j = 0 ; j < n ; ++ j ) { if ( i != j ) { if ( t [ j ]. containsAll ( t [ i ])) { ok = false ; break ; } } } if ( ok ) { ans . add ( i ); } } return ans ; } }

1class Solution {2public:3  vector<int> peopleIndexes(vector<vector<string>> &favoriteCompanies) {4    unordered_map<string, int> d;5    int idx = 0, n = favoriteCompanies.size();6    vector<unordered_set<int>> t(n);7    for (int i = 0; i < n; ++i) {8      auto v = favoriteCompanies[i];9      for (auto &c : v) {10        if (!d.count(c)) {11          d[c] = idx++;12        }13      }14      unordered_set<int> s;15      for (auto &c : v) {16        s.insert(d[c]);17      }18      t[i] = s;19    }20    vector<int> ans;21    for (int i = 0; i < n; ++i) {22      bool ok = true;23      for (int j = 0; j < n; ++j) {24        if (i == j)25          continue;26        if (check(t[i], t[j])) {27          ok = false;28          break;29        }30      }31      if (ok) {32        ans.push_back(i);33      }34    }35    return ans;36  }37  bool check(unordered_set<int> &nums1, unordered_set<int> &nums2) {38    for (int v : nums1) {39      if (!nums2.count(v)) {40        return false;41      }42    }43    return true;44  }45};

1class Solution:2    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]: d = {} idx = 0 t = [] for v in favoriteCompanies: for c in v: if c not in d: d[c] = idx idx += 1 t . append({d[c] for c in v}) ans = [] for i, nums1 in enumerate(t): ok = True for j, nums2 in enumerate(t): if i == j: continue if not (nums1 - nums2): ok = False break if ok: ans . append(i) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem