Problem Description

You are given an array favoriteCompanies where favoriteCompanies[i] contains the list of favorite companies for the i-th person (0-indexed).

Your task is to find all people whose list of favorite companies is not a subset of any other person's list of favorite companies. Return the indices of these people in increasing order.

In other words, for each person, check if their favorite companies list is completely contained within someone else's favorite companies list. If a person's favorites are not fully contained in anyone else's list, include their index in the result.

For example:

• If person 0 has favorites ["leetcode", "google"]
• And person 1 has favorites ["leetcode", "google", "facebook"]
• Then person 0's favorites are a subset of person 1's favorites (all companies in person 0's list appear in person 1's list)
• So person 0 would not be included in the answer, but person 1 might be (depending on other people's lists)

The solution approach converts company names to unique integers for efficient comparison. It creates sets of integers for each person's favorite companies, then checks if any person's set is a subset of another person's set using set operations. The condition (nums[i] & nums[j]) == nums[i] checks if nums[i] is a subset of nums[j] by verifying if their intersection equals nums[i].

Intuition

The key insight is recognizing that checking if one list is a subset of another is fundamentally a set operation problem. When we need to determine if all elements of list A exist in list B, we're essentially asking: is A a subset of B?

Initially, we might think to compare the string lists directly, but string comparisons are expensive, especially when done repeatedly. Each string comparison takes time proportional to the string length, and we'd need to do this for every company name when checking subsets.

This leads us to a clever optimization: what if we could convert these strings to numbers? Numbers can be compared in constant time, making our subset checks much faster. We can create a mapping where each unique company name gets assigned a unique integer ID. For example, "google" might become 0, "facebook" becomes 1, and so on.

Once we have this mapping, each person's favorite companies can be represented as a set of integers instead of a set of strings. Now the subset check becomes elegant: for person i to be a subset of person j, every number in person i's set must also be in person j's set.

The mathematical property we exploit is that if set A is a subset of set B, then the intersection of A and B equals A itself. In code terms: A ∩ B = A means A is a subset of B. This gives us an efficient way to check the subset relationship using the expression (nums[i] & nums[j]) == nums[i].

Finally, for each person, we check against all other people. If we find even one other person whose favorites contain all of our current person's favorites, then the current person's list is a subset and shouldn't be included in the answer. Only those whose lists are not subsets of any other list make it to the final result.

Solution Approach

The implementation follows a three-phase approach: mapping, conversion, and subset checking.

Phase 1: String to Integer Mapping

We start by creating a dictionary d to map each unique company name to a unique integer ID. We also initialize:

• idx = 0 as a counter for assigning unique IDs
• n = len(favoriteCompanies) to store the number of people
• nums as a list of n empty sets to store integer representations of each person's favorites

idx = 0
d = {}
n = len(favoriteCompanies)
nums = [set() for _ in range(n)]

Phase 2: Convert Company Names to Integer Sets

We iterate through each person's favorite companies. For each company name:

• If it's not in our dictionary, we assign it a new unique ID and increment idx
• We add the company's integer ID to the corresponding person's set in nums

for i, ss in enumerate(favoriteCompanies):
    for s in ss:
        if s not in d:
            d[s] = idx
            idx += 1
        nums[i].add(d[s])

After this phase, each person's favorite companies are represented as a set of integers. For example, if person 0 likes ["google", "leetcode"] and these map to {0, 1}, then nums[0] = {0, 1}.

Phase 3: Subset Checking

For each person i, we check if their set is a subset of any other person j's set:

ans = []
for i in range(n):
    if not any(i != j and (nums[i] & nums[j]) == nums[i] for j in range(n)):
        ans.append(i)

The key expression (nums[i] & nums[j]) == nums[i] checks if nums[i] is a subset of nums[j]:

• nums[i] & nums[j] computes the intersection (common elements)
• If this intersection equals nums[i], it means all elements of nums[i] are in nums[j]
• The condition i != j ensures we don't compare a person with themselves

The any() function returns True if at least one person j has nums[i] as a subset. We use not any() to find people whose favorites are NOT a subset of anyone else's.

The time complexity is O(n² × m) where n is the number of people and m is the average size of favorite company lists, as we need to check each pair of people and perform set operations.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input:

favoriteCompanies = [
    ["leetcode", "google", "facebook"],
    ["google", "microsoft"],
    ["google", "facebook"],
    ["google"],
    ["amazon"]
]

Phase 1: Create String to Integer Mapping

We build a dictionary to map company names to unique integers:

• "leetcode" → 0
• "google" → 1
• "facebook" → 2
• "microsoft" → 3
• "amazon" → 4

Phase 2: Convert to Integer Sets

Transform each person's favorites into sets of integers:

• Person 0: ["leetcode", "google", "facebook"] → {0, 1, 2}
• Person 1: ["google", "microsoft"] → {1, 3}
• Person 2: ["google", "facebook"] → {1, 2}
• Person 3: ["google"] → {1}
• Person 4: ["amazon"] → {4}

Phase 3: Check for Subsets

Now we check if each person's set is a subset of any other person's set:

Person 0 with set {0, 1, 2}:

• vs Person 1: {0, 1, 2} ∩ {1, 3} = {1} ≠ {0, 1, 2} → Not a subset
• vs Person 2: {0, 1, 2} ∩ {1, 2} = {1, 2} ≠ {0, 1, 2} → Not a subset
• vs Person 3: {0, 1, 2} ∩ {1} = {1} ≠ {0, 1, 2} → Not a subset
• vs Person 4: {0, 1, 2} ∩ {4} = {} ≠ {0, 1, 2} → Not a subset
• Result: Person 0 is not a subset of anyone else ✓

Person 1 with set {1, 3}:

• vs Person 0: {1, 3} ∩ {0, 1, 2} = {1} ≠ {1, 3} → Not a subset
• vs Person 2: {1, 3} ∩ {1, 2} = {1} ≠ {1, 3} → Not a subset
• vs Person 3: {1, 3} ∩ {1} = {1} ≠ {1, 3} → Not a subset
• vs Person 4: {1, 3} ∩ {4} = {} ≠ {1, 3} → Not a subset
• Result: Person 1 is not a subset of anyone else ✓

Person 2 with set {1, 2}:

• vs Person 0: {1, 2} ∩ {0, 1, 2} = {1, 2} = {1, 2} → Is a subset!
• Result: Person 2 is a subset of Person 0 ✗

Person 3 with set {1}:

• vs Person 0: {1} ∩ {0, 1, 2} = {1} = {1} → Is a subset!
• Result: Person 3 is a subset of Person 0 ✗

Person 4 with set {4}:

• vs Person 0: {4} ∩ {0, 1, 2} = {} ≠ {4} → Not a subset
• vs Person 1: {4} ∩ {1, 3} = {} ≠ {4} → Not a subset
• vs Person 2: {4} ∩ {1, 2} = {} ≠ {4} → Not a subset
• vs Person 3: {4} ∩ {1} = {} ≠ {4} → Not a subset
• Result: Person 4 is not a subset of anyone else ✓

Final Answer: [0, 1, 4]

The people at indices 0, 1, and 4 have favorite company lists that are not subsets of any other person's list.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × m × k + n² × m)

The time complexity consists of two main parts:

• Building the mapping dictionary and converting strings to numbers: O(n × m × k), where we iterate through n people, each with an average of m favorite companies, and each company string has an average length of k characters (for dictionary operations).
• Checking if each person's set is a subset of any other person's set: O(n² × m), where for each of the n people, we check against all other n-1 people, and each subset check (nums[i] & nums[j]) == nums[i] takes O(m) time in the worst case.

Space Complexity: O(n × m)

The space complexity comes from:

• Dictionary d storing all unique company strings: O(n × m) in the worst case when all companies are unique
• List nums containing n sets, where each set contains at most m company indices: O(n × m)
• Output list ans: O(n) in the worst case

The dominant space factor is O(n × m).

Here, n is the number of people (length of favoriteCompanies), m is the average number of companies per person, and k is the average length of each company name string.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Subset Check Logic

A common mistake is checking if nums[j] is a subset of nums[i] instead of checking if nums[i] is a subset of nums[j]. This reversal would give completely wrong results.

Incorrect:

# Wrong: This checks if j is a subset of i
if (nums[j] & nums[i]) == nums[j]:
    is_subset_of_another = True

Correct:

# Right: This checks if i is a subset of j
if (nums[i] & nums[j]) == nums[i]:
    is_subset_of_another = True
# Or more clearly:
if nums[i].issubset(nums[j]):
    is_subset_of_another = True

2. String Comparison Instead of Set Operations

Attempting to directly compare lists of strings without converting to sets leads to incorrect results, as list comparison checks order and exact equality, not subset relationships.

Incorrect:

# Wrong: Lists don't have subset operations
for i in range(n):
    is_subset = False
    for j in range(n):
        if i != j and all(company in favoriteCompanies[j] for company in favoriteCompanies[i]):
            is_subset = True
            break

This approach has O(n² × m²) complexity due to nested string searches and may fail with duplicate companies in lists.

Correct:

# Convert to sets first for O(1) membership checks
company_sets = [set(companies) for companies in favoriteCompanies]
for i in range(n):
    if not any(i != j and company_sets[i].issubset(company_sets[j]) for j in range(n)):
        result.append(i)

3. Forgetting Self-Comparison Check

Omitting the i != j condition causes every person's set to be considered a subset of itself, resulting in an empty answer list.

Incorrect:

# Wrong: Every set is a subset of itself
for i in range(n):
    if not any((nums[i] & nums[j]) == nums[i] for j in range(n)):
        ans.append(i)
# This will always return an empty list

Correct:

# Must exclude self-comparison
for i in range(n):
    if not any(i != j and (nums[i] & nums[j]) == nums[i] for j in range(n)):
        ans.append(i)

4. Unnecessary String-to-Integer Mapping

While the original solution maps strings to integers, this step is actually unnecessary since Python's set operations work efficiently with strings. The mapping adds complexity without significant performance benefit for this problem.

Overcomplicated:

# Unnecessary mapping phase
company_to_id = {}
next_id = 0
company_id_sets = [set() for _ in range(num_people)]
for person_idx, companies in enumerate(favoriteCompanies):
    for company in companies:
        if company not in company_to_id:
            company_to_id[company] = next_id
            next_id += 1
        company_id_sets[person_idx].add(company_to_id[company])

Simplified:

# Direct set conversion is cleaner and equally efficient
company_sets = [set(companies) for companies in favoriteCompanies]
result = []
for i in range(len(company_sets)):
    if not any(i != j and company_sets[i].issubset(company_sets[j]) 
               for j in range(len(company_sets))):
        result.append(i)

The simplified version maintains O(n² × m) complexity while being more readable and less error-prone.