LeetCode 1452 - People Whose List of Favorite Companies Is Not a Subset of Another List

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String

Solution

Problem Understanding

The problem requires identifying all people in a group whose list of favorite companies is not a subset of any other person's list. Each person has a list of companies they like, and we want the indices of people whose lists are unique in the sense that no other list completely contains theirs.

The input is a 2D array favoriteCompanies, where favoriteCompanies[i] is the list of companies person i likes. The output is a sorted list of indices of people who do not have their list entirely contained in someone else's list.

Constraints provide important guidance on the scale and structure of the input: the number of people (favoriteCompanies.length) is up to 100, and each person's list can contain up to 500 companies. Each string is distinct and lowercase. Importantly, the lists themselves are all distinct, so we do not have duplicate lists to worry about.

Edge cases that may cause naive implementations to fail include lists that are empty (though constraints guarantee at least one company per list), lists that have a single element, or lists that are subsets of multiple other lists. The guarantees prevent duplicates and empty strings, which simplifies handling.

Approaches

Brute Force

A brute-force approach would check every pair of lists (i, j) and see if favoriteCompanies[i] is a subset of favoriteCompanies[j]. This requires iterating over each element in i and checking membership in j, which could be done using lists, but is slow. For n people and up to m companies per person, this is O(n^2 * m) time complexity. It works because it directly tests the subset property for each pair but is inefficient because many membership checks are repeated.

Optimal Approach

The key insight is that checking subset membership is faster using sets. By converting each person's company list into a set, we can check subset membership in O(1) average time per element. Then, we iterate over all pairs (i, j) and check if i is a subset of j. If no j fully contains i, we include i in the answer.

This approach is simple, leverages Python's (or Go's) set operations for fast subset checks, and avoids manually iterating over lists for membership tests.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2 * m)	O(1)	Directly checks subset using list membership
Optimal	O(n^2 * m)	O(n * m)	Uses sets to speed up subset checks, same asymptotic time but faster in practice

Algorithm Walkthrough

Convert each person's list of favorite companies into a set. This allows for constant-time membership checks.
Initialize an empty list result to store indices of people whose lists are not subsets.
For each person i, assume their list is not a subset (is_subset = False).
Compare i's set with every other person's set j. Skip if i == j.
If i's set is a subset of j's set, mark is_subset = True and break out of the inner loop.
After checking all other sets, if is_subset remains False, append i to result.
Return the sorted result.

Why it works: The algorithm systematically checks the subset property against all other lists. Since we mark and exclude lists that are subsets of any other, the final result only contains indices where the list is unique in this sense. The use of sets guarantees that subset checks are correct and efficient.

Python Solution

from typing import List

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        company_sets = [set(companies) for companies in favoriteCompanies]
        result = []
        
        for i, comp_set_i in enumerate(company_sets):
            is_subset = False
            for j, comp_set_j in enumerate(company_sets):
                if i != j and comp_set_i.issubset(comp_set_j):
                    is_subset = True
                    break
            if not is_subset:
                result.append(i)
                
        return result

Explanation: We first convert all lists to sets for fast subset checks. Then, for each person, we compare their set to all other sets. If the current person's set is not a subset of any other, we add their index to result. Using issubset ensures correctness and readability.

Go Solution

func peopleIndexes(favoriteCompanies [][]string) []int {
    n := len(favoriteCompanies)
    companySets := make([]map[string]struct{}, n)
    for i := 0; i < n; i++ {
        companySets[i] = make(map[string]struct{})
        for _, company := range favoriteCompanies[i] {
            companySets[i][company] = struct{}{}
        }
    }

    result := []int{}
    for i := 0; i < n; i++ {
        isSubset := false
        for j := 0; j < n; j++ {
            if i == j {
                continue
            }
            subset := true
            for company := range companySets[i] {
                if _, exists := companySets[j][company]; !exists {
                    subset = false
                    break
                }
            }
            if subset {
                isSubset = true
                break
            }
        }
        if !isSubset {
            result = append(result, i)
        }
    }

    return result
}

Go-specific notes: Go uses maps to simulate sets, so subset checking requires iterating through the keys of companySets[i]. Empty structs are used to save memory. Otherwise, the logic mirrors Python.

Worked Examples

Example 1

Input: [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]]

Convert each list to a set.
Person 0 set: {leetcode, google, facebook} - not subset of anyone else.
Person 1 set: {google, microsoft} - not subset of anyone else.
Person 2 set: {google, facebook} - subset of person 0 → skip.
Person 3 set: {google} - subset of person 0 and 1 → skip.
Person 4 set: {amazon} - not subset of anyone else.

Output: [0,1,4]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2 * m)	Each of n people is compared to n others; subset check iterates over up to m companies
Space	O(n * m)	Storing sets for each person

Despite the same asymptotic time as brute force, the use of sets makes membership checks faster in practice.

Test Cases

# Provided examples
assert Solution().peopleIndexes([["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]]) == [0,1,4]
assert Solution().peopleIndexes([["leetcode","google","facebook"],["leetcode","amazon"],["facebook","google"]]) == [0,1]
assert Solution().peopleIndexes([["leetcode"],["google"],["facebook"],["amazon"]]) == [0,1,2,3]

# Edge cases
assert Solution().peopleIndexes([["a","b"], ["a"], ["b"]]) == [0,1,2]  # none is subset of both
assert Solution().peopleIndexes([["a"], ["a","b"], ["a","b","c"]]) == [2]  # only largest set survives
assert Solution().peopleIndexes([["a"]]) == [0]  # single person

Test	Why
["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]	Tests multiple subsets across different lists
["leetcode","google","facebook"],["leetcode","amazon"],["facebook","google"]	Tests subset detection when order varies
["leetcode"],["google"],["facebook"],["amazon"]	Tests no subsets at all
["a","b"], ["a"], ["b"]	Ensures subsets are correctly identified individually
["a"], ["a","b"], ["a","b","c"]	Tests chain of subsets
["a"]	Single element input

Edge Cases

One edge case is when all lists have only one company. Each company is distinct, so each person will remain in the result. Another is a chain of subsets, such as [["a"], ["a","b"], ["a","b","c"]], where only the largest set remains; the algorithm correctly checks against all other lists and filters out subsets. A final edge case is when multiple lists could be subsets of more than one other list; the algorithm stops at the first detected superset and correctly avoids redundant checks. The guarantees of distinct lists and non-empty elements prevent index errors or duplicate handling.