#1452

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

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

Identify people whose favorite companies lists are unique and not subsets of any other person's list using efficient array and hash techniques.

array hash table string

Problem Statement

Given a list favoriteCompanies where favoriteCompanies[i] contains the favorite companies of the ith person, return all indices of people whose list is not a subset of any other person's list. Each list contains unique company names, and the result must be returned in increasing order.

For example, favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]] yields [0,1,4] because some lists are proper subsets of others, while others remain unique.

Examples

Example 1

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

Output: [0,1,4]

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]

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]

Example details omitted.

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.

Solution Approach

Convert Lists to Hash Sets

Transform each person's favoriteCompanies list into a hash set to allow O(1) lookup for subset checks. This ensures faster comparisons and avoids repeated linear scans when checking if one list is contained in another.

Compare Each List Against All Others

Iterate through each list and check against all other lists. If any list is a superset of the current list, mark the current index as a subset. Skip unnecessary comparisons once a subset relationship is found to reduce overhead.

Collect Non-Subset Indices

After checking all subset relationships, collect indices where the list was never found to be a subset of another. Return the indices in sorted order to meet the problem requirements.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2 * m) in the worst case, where n is the number of people and m is the average number of companies per list, due to pairwise subset checks. Space complexity is O(n * m) for storing hash sets of each list.

What Interviewers Usually Probe

You might get hints about using hashing for subset checks to avoid TLE.
Expect questions on handling large lists and optimizing comparisons.
Clarify whether duplicate company names exist and confirm subset definitions.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle lists with identical companies correctly and treating them as subsets.
Not converting lists to sets, which leads to O(n * m^2) time complexity.
Returning indices unsorted, which violates problem requirements.

Follow-up variants

Return lists that are subsets of at least one other list instead of non-subsets.
Find non-subset lists but return them as company names instead of indices.
Optimize for memory by using bitmask encoding for smaller alphabets of company names.

FAQ

What pattern does this problem use?

It follows the array scanning plus hash lookup pattern, where each list is converted to a set and checked against others for subset relations.

Can favoriteCompanies contain duplicates within a single list?

No, all strings within a list are distinct, so subset checks do not need to handle duplicates.

How should the output indices be returned?

Indices must be returned in increasing order as specified in the problem.

What is a common optimization to prevent O(n^2 * m) bottlenecks?

Use hash sets for each list and skip comparisons once a subset is detected to reduce unnecessary checks.

Does GhostInterview help identify lists that are proper subsets?

Yes, it flags any list that is a subset of another and ensures only non-subset indices are returned efficiently.

terminal

Solution

Solution 1: Hash Table

We can map each company to a unique integer. Then, for each person, we convert their favorite companies into a set of integers. Finally, we check if the favorite companies of one person are a subset of another person's favorite companies.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        idx = 0
        d = {}
        n = len(favoriteCompanies)
        nums = [set() for _ in range(n)]
        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])
        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)
        return ans

Continue Practicing

#1436 destination city #1418 display table of food orders in a restaurant #1487 making file names unique