# People Whose List of Favorite Companies Is Not a Subset of Another List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list)
Canonical: https://scaleengineer.com/dsa/problems/people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list
**Data structures:** Array, Hash Table, String
**Companies:** [Datadog](https://scaleengineer.com/companies/datadog)
---
## 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 <= 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
## Brute-Force with Hash Sets
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.
**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.
**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.
### Explanation
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:

1.  Create a list of `HashSet<String>` from the input `favoriteCompanies`.
2.  Iterate through each person `i`.
3.  For each `i`, iterate through all other people `j`.
4.  If `list[i]` is a subset of `list[j]`, we mark `i` as a subset and move to the next person.
5.  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.

```java
import java.util.*;

class Solution {
    public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
        int n = favoriteCompanies.size();
        List<Set<String>> companySets = new ArrayList<>();
        for (List<String> companies : favoriteCompanies) {
            companySets.add(new HashSet<>(companies));
        }

        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            boolean isSubset = false;
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                // A list can only be a proper subset of a larger list.
                if (companySets.get(i).size() >= companySets.get(j).size()) {
                    continue;
                }
                // Check if set i is a subset of set j
                if (companySets.get(j).containsAll(companySets.get(i))) {
                    isSubset = true;
                    break;
                }
            }
            if (!isSubset) {
                result.add(i);
            }
        }
        return result;
    }
}
```
### 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.

## Optimized Approach with Integer Mapping
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.
**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.
**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.
### Explanation
This method improves upon the brute-force approach by reducing the cost of comparisons inside the nested loops.

1.  **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.

2.  **Integer Set Creation:** We then create a new list of sets, where each set contains the integer IDs of a person's favorite companies.

3.  **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.

```java
import java.util.*;

class Solution {
    public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
        // 1. Map strings to integers and create integer sets
        Map<String, Integer> companyToInt = new HashMap<>();
        int nextId = 0;
        List<Set<Integer>> companyIntSets = new ArrayList<>();

        for (List<String> companies : favoriteCompanies) {
            Set<Integer> currentSet = new HashSet<>();
            // Sort companies to potentially improve cache performance, though not strictly necessary for correctness
            // Collections.sort(companies);
            for (String company : companies) {
                if (!companyToInt.containsKey(company)) {
                    companyToInt.put(company, nextId++);
                }
                currentSet.add(companyToInt.get(company));
            }
            companyIntSets.add(currentSet);
        }

        // 2. Perform subset check on integer sets
        int n = favoriteCompanies.size();
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            boolean isSubset = false;
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                Set<Integer> setI = companyIntSets.get(i);
                Set<Integer> setJ = companyIntSets.get(j);

                if (setI.size() >= setJ.size()) {
                    continue;
                }
                
                if (setJ.containsAll(setI)) {
                    isSubset = true;
                    break;
                }
            }
            if (!isSubset) {
                result.add(i);
            }
        }
        
        return result;
    }
}
```
### 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.

# Solutions
### Java

```java
class 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 ; } }
```

### CPP

```cpp
class Solution {
public:
  vector<int> peopleIndexes(vector<vector<string>> &favoriteCompanies) {
    unordered_map<string, int> d;
    int idx = 0, n = favoriteCompanies.size();
    vector<unordered_set<int>> t(n);
    for (int i = 0; i < n; ++i) {
      auto v = favoriteCompanies[i];
      for (auto &c : v) {
        if (!d.count(c)) {
          d[c] = idx++;
        }
      }
      unordered_set<int> s;
      for (auto &c : v) {
        s.insert(d[c]);
      }
      t[i] = s;
    }
    vector<int> ans;
    for (int i = 0; i < n; ++i) {
      bool ok = true;
      for (int j = 0; j < n; ++j) {
        if (i == j)
          continue;
        if (check(t[i], t[j])) {
          ok = false;
          break;
        }
      }
      if (ok) {
        ans.push_back(i);
      }
    }
    return ans;
  }
  bool check(unordered_set<int> &nums1, unordered_set<int> &nums2) {
    for (int v : nums1) {
      if (!nums2.count(v)) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    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

```