Problem Description

The Leetcode problem "People Whose List of Favorite Companies Is Not a Subset of Another List" asks you to process a list where each person has a list of their favorite companies. You are to find all people whose list of favorite companies is not a subset of any other person's list.

More formally: Given a list favoriteCompanies where favoriteCompanies[i] is a list of strings representing the favorite companies of the i-th person, return the indices of all people whose list is not a subset of any other person's list. The result can be in any order.

• Each person’s list contains unique company names.
• There is only one valid solution for each input.
• You must not reuse elements; each person's list is considered independently.

Thought Process

At first glance, the problem seems to require comparing each person's list to every other person's list to check if it's a subset. This would mean, for every person, checking all other people and performing a subset check. This is a classic brute-force approach.

However, this can be inefficient, especially if there are many people or large lists. We want to optimize the subset checking. Since each list contains unique companies, and company names are strings, we can use sets to leverage fast subset operations. We can also consider ways to avoid unnecessary comparisons, such as skipping comparisons for lists of smaller size, or pre-processing the data.

The key insight is to use set operations for subset checking and to minimize redundant work by only comparing relevant pairs.

Solution Approach

We approach the problem step-by-step:

1. Convert each person's list to a set:
   • This allows us to use the issubset or equivalent operation in O(1) for each comparison (on average).
2. For each person, compare their set to every other person's set:
   • If the current person's set is a subset of any other person's set (and not the same set), we mark them as a subset.
3. Collect the indices of people who are not subsets of anyone else:
   • Return these indices as the answer.
4. Optimization:
   • Since a set can only be a subset of another set if the other set is the same size or larger, we can skip comparisons where the candidate set is smaller.

This approach is clean and leverages data structures (sets) for efficient subset checking.

Example Walkthrough

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

1. Person 0: ["leetcode","google","facebook"]
   • Is this list a subset of any other?
   • Compare with each other person's list: No, because no other person has all three companies.
2. Person 1: ["google","microsoft"]
   • Is a subset of no one else.
3. Person 2: ["google","facebook"]
   • Is a subset of Person 0's list.
   • So, Person 2 is excluded.
4. Person 3: ["google"]
   • Is a subset of Person 0, Person 1, and Person 2.
   • So, Person 3 is excluded.
5. Person 4: ["amazon"]
   • Is a subset of no one else.

Final answer: indices [0,1,4].

Code Implementation

class Solution:
    def peopleIndexes(self, favoriteCompanies):
        n = len(favoriteCompanies)
        sets = [set(companies) for companies in favoriteCompanies]
        res = []
        for i in range(n):
            is_subset = False
            for j in range(n):
                if i != j and sets[i].issubset(sets[j]):
                    is_subset = True
                    break
            if not is_subset:
                res.append(i)
        return res
      

class Solution {
public:
    vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
        int n = favoriteCompanies.size();
        vector<set<string>> sets;
        for (auto& companies : favoriteCompanies) {
            sets.push_back(set<string>(companies.begin(), companies.end()));
        }
        vector<int> res;
        for (int i = 0; i < n; ++i) {
            bool is_subset = false;
            for (int j = 0; j < n; ++j) {
                if (i != j) {
                    // check if i's set is subset of j's set
                    bool subset = true;
                    for (const string& company : sets[i]) {
                        if (sets[j].find(company) == sets[j].end()) {
                            subset = false;
                            break;
                        }
                    }
                    if (subset) {
                        is_subset = true;
                        break;
                    }
                }
            }
            if (!is_subset) res.push_back(i);
        }
        return res;
    }
};
      

import java.util.*;
class Solution {
    public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
        int n = favoriteCompanies.size();
        List<Set<String>> sets = new ArrayList<>();
        for (List<String> companies : favoriteCompanies) {
            sets.add(new HashSet<>(companies));
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            boolean isSubset = false;
            for (int j = 0; j < n; ++j) {
                if (i != j && sets.get(j).containsAll(sets.get(i))) {
                    isSubset = true;
                    break;
                }
            }
            if (!isSubset) res.add(i);
        }
        return res;
    }
}
      

var peopleIndexes = function(favoriteCompanies) {
    let n = favoriteCompanies.length;
    let sets = favoriteCompanies.map(list => new Set(list));
    let res = [];
    for (let i = 0; i < n; ++i) {
        let isSubset = false;
        for (let j = 0; j < n; ++j) {
            if (i !== j) {
                // Check if i's set is subset of j's set
                let subset = true;
                for (let company of sets[i]) {
                    if (!sets[j].has(company)) {
                        subset = false;
                        break;
                    }
                }
                if (subset) {
                    isSubset = true;
                    break;
                }
            }
        }
        if (!isSubset) res.push(i);
    }
    return res;
};
      

Time and Space Complexity

• Brute-force approach:
  • For each person, compare their list to every other person's list. For each comparison, check if all companies are present, which is O(L), where L is the length of the list.
  • So, overall time complexity is O(N^2 * L), where N is the number of people, and L is the average list length.
• Optimized approach (using sets):
  • Set operations like issubset are on average O(L), so the overall time complexity remains O(N^2 * L) in the worst case, but the constant factor is improved by using efficient set lookups.
  • Space complexity is O(N * L) to store the sets.

The approach is efficient for the input size constraints typically found on Leetcode for this problem.

Summary

This problem is a classic example of subset checking between collections. By representing each person's list as a set, we can efficiently check for subset relationships using built-in set operations. The solution iterates over all pairs of people, checks for subset relationships, and collects the indices of people whose lists are not subsets of any other. The approach is simple, leverages the properties of sets, and is both easy to implement and understand.