Skip to main content
Talentd

People Whose List of Favorite Companies Is Not a Subset of Another List - Solution & Explanation

MediumArrayHash TableString16 min readAsked at: Datadog, Google
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You receive a list where favoriteCompanies[i] contains the companies liked by the i-th person. The task is to return the indices of people whose list is not a subset of any other person's list. In other words, if every company in person A's list also appears in person B's list, then A should be excluded.

Approach 1: Brute Force Comparison (O(n2 * k) time, O(k) space)

Compare every person's company list with every other person's list. For each pair (i, j), check whether all companies in favoriteCompanies[i] exist in favoriteCompanies[j]. Converting the second list to a hash set makes membership checks O(1). If every company in i exists in j, then i is a subset and should be excluded from the result. This method directly implements the definition of subset using nested iteration and works reliably for moderate input sizes.

The key operation is repeated membership testing. Without hashing, checking membership would require scanning strings in the list each time, leading to much slower comparisons. Using a set ensures each lookup runs in constant time while iterating through company names. This approach is conceptually simple and demonstrates clear understanding of subset logic using arrays and strings.

Approach 2: Optimized Subset Checking with Early Termination (O(n2 * k) time, O(n * k) space)

First convert every person's company list into a HashSet. This preprocessing allows fast subset checks later. Then iterate over all pairs of people. When checking if set A is a subset of set B, immediately stop once a company from A is missing in B. Early termination significantly reduces comparisons when lists differ early.

Another small optimization is skipping comparisons where A is larger than B. A larger set cannot be a subset of a smaller one. This reduces unnecessary checks and improves average performance while maintaining the same worst‑case complexity. The approach relies heavily on efficient membership operations provided by hash tables.

Recommended for interviews: The optimized hash‑set subset comparison is typically expected. Interviewers want to see you translate the subset condition into efficient set operations. Starting with the brute force explanation shows clear reasoning, but switching to hashed sets and early termination demonstrates stronger algorithmic thinking and practical optimization.

Approach 1: Brute Force Comparison

This approach involves comparing each person's list of favorite companies with every other person's list to check if one is a subset of the other. By iterating through each pair of lists, we determine the subset relationships.

We then collect the indices of those lists which are not subsets of any other list.

This C program defines a helper function isSubset to determine if one list of favorite companies is a subset of another. It then iterates over all possible pairs of lists and utilizes this helper function to check their subset relationship.

The main function, peopleNotSubset, builds a list of all indices whose favorite companies are not a subset of any other's favorite companies, returning that list.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2 * m), where n is the number of lists and m is the average number of companies in each list. This comes from comparing each list to every other list.

Space Complexity: O(n), needed for storing the result indices.

Try this approach in the editor →

Approach 2: Optimized Subset Checking with Early Termination

An optimized approach is to sort the lists based on their lengths and check smaller lists against larger ones first. By doing this, we can potentially terminate the checking early if a subset relationship is found quicker.

Only necessary comparisons are made, possibly reducing the average number of checks.

This C approach first sorts the indices of the favorite companies based on the list lengths. By processing shorter lists first, it ensures that any potential subsets are identified rapidly without unnecessary comparisons, optimizing the runtime.

Code

C

C

Complexity

Time Complexity: O(n^2 * m) due to sorting and comparison calls, but usually performs faster compared to naive approach due to short-circuit conditions.

Space Complexity: O(n) for indices and result storage arrays.

Try this approach in the editor →

Approach 3: 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.

The time complexity is (n times m times k + n^2 times m), and the space complexity is O(n times m). Here, n and m are the lengths of favoriteCompanies and the average length of each company's list, respectively, and k is the average length of each company.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Comparison

Time Complexity: O(n^2 * m), where n is the number of lists and m is the average number of companies in each list. This comes from comparing each list to every other list.

Space Complexity: O(n), needed for storing the result indices.

Optimized Subset Checking with Early Termination

Time Complexity: O(n^2 * m) due to sorting and comparison calls, but usually performs faster compared to naive approach due to short-circuit conditions.

Space Complexity: O(n) for indices and result storage arrays.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ComparisonO(n^2 * k)O(k)Simple baseline solution; good for understanding subset relationships
Hash Set Subset CheckO(n^2 * k)O(n * k)General case with faster membership checks using hash tables
Optimized with Early TerminationO(n^2 * k) worst caseO(n * k)Preferred in interviews; skips unnecessary comparisons and stops early when mismatch appears

Video Solution

1452 People Whose List of Favorite Companies Is Not a Subset of Another List || Weekly Contest 189 • code Explainer • 1,101 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is People Whose List of Favorite Companies Is Not a Subset of Another List easy or hard?
The problem is rated Medium because the core idea is simple but requires careful implementation. Recognizing the subset relationship and optimizing comparisons with hash sets is the key step that elevates it beyond an easy problem.
People Whose List of Favorite Companies Is Not a Subset of Another List Python/Java solution
In Python, convert each list to a set and use set operations like subset checks or manual iteration with membership tests. In Java, use HashSet<String> for each list and compare sets using contains checks. Both implementations follow the same O(n^2 * k) approach.
How to solve People Whose List of Favorite Companies Is Not a Subset of Another List in O(n)?
An O(n) solution is generally not feasible because each person's list must potentially be compared with many others to verify subset relationships. The practical solution uses pairwise comparisons with hash sets, resulting in O(n^2 * k) complexity.
What is the best approach for People Whose List of Favorite Companies Is Not a Subset of Another List?
The most practical approach converts each person's company list into a hash set and compares it against other sets. For each pair of people, check if one set is a subset of another and terminate early when a missing company is found. This method runs in O(n^2 * k) time with O(n * k) space, where k is the average list length.
Is People Whose List of Favorite Companies Is Not a Subset of Another List asked at Google/Amazon/Meta?
Subset and set‑comparison problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The question tests understanding of hash sets, efficient membership checks, and careful pairwise comparison logic.
What data structure is used in People Whose List of Favorite Companies Is Not a Subset of Another List?
Hash sets are the primary data structure used. Each list of company names is converted into a set so that membership checks run in constant time. Arrays store the original lists, while hash tables enable fast subset verification.
What is the time complexity of People Whose List of Favorite Companies Is Not a Subset of Another List?
The standard solution runs in O(n^2 * k) time. You compare every pair of people (n^2) and check up to k companies when verifying subset relationships. Using hash sets keeps membership checks O(1), making the comparison efficient.

Ready to solve this problem?

Practice People Whose List of Favorite Companies Is Not a Subset of Another List with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays