1452. People Whose List of Favorite Companies Is Not a Subset of Another List
Problem Description
In this problem, we are given an array favoriteCompanies
where favoriteCompanies[i]
represents the list of favorite companies for the ith
person, with indexing starting from 0. The task is to find out which individuals have a list of favorite companies that is unique and not simply a subset of any other person's list of favorite companies. In other words, we need to identify people with favorite company lists that contain at least one company not listed in any other person's favorite list. The output should be the list of indices of such people, sorted in increasing order.
Intuition
The intuition behind the solution involves understanding the concept of subsets. If a list of favorite companies for a person is a subset of another person's list, it means all companies liked by the first person are also liked by the second person. We want to find those people whose lists are not entirely contained within another's list.
To achieve this, we can use a set data structure to efficiently test if one set is a subset of another. The basic approach to solve this problem goes as follows:
-
Create a hash map (dictionary in Python) to hold a unique index for each company. This is a way of converting the company names from strings to integers, thus enabling us to perform set operations more efficiently.
-
Convert each person's favorite company list into a set of integers using the hash map created in the previous step. In the process, we map each company to its unique integer index and construct a set for each person. This step is crucial because it allows us to use fast set operations like union, intersection, and difference.
-
Iterate over each person's set and compare it with every other person's set to check whether it's not a subset of any other. During iteration, if we find that person
i
's set is not a subset of any other personj
's set (i != j
), we consider it as a unique list. -
Whenever we find such a unique list, we record the index of that person. After processing all people, we should have the indices of those with unique favorite company lists.
-
Return the list of indices that we have recorded.
This algorithm shifts the focus from working with strings to working with integers and sets, which is typically more efficient and simpler. Additionally, by early exiting the inner loop when we find a subset, we save time that would otherwise be wasted on unnecessary comparisons.
Solution Approach
The Reference Solution Approach provided above offers a clear pathway for implementing a solution to the problem. Here's a step-by-step explanation of the solution:
-
Hash Map Creation: The algorithm begins by creating a hash map named
d
which maps every company to a unique integer. This allows for efficient set operations later on. The hash map is populated as follows:- Iterate over every person's favorite company list.
- For every company not already in the hash map, add it with an incrementing index (
idx
).
-
Conversion to Integer Sets: For every person, their favorite companies list is then converted into a set of integers,
t
. The conversion process involves:- For each company in the person's list, find its corresponding index in the hash map
d
. - Construct a set of these indices.
- For each company in the person's list, find its corresponding index in the hash map
-
Unique Lists Identification: With the integer sets prepared, the next step is to determine which sets are unique, i.e., not subsets of any other sets. This is done by:
- Iterating over every set (
nums1
) int
. - Checking
nums1
against every other set (nums2
) int
. - Using set difference (
nums1 - nums2
), determine ifnums1
is a subset ofnums2
. Ifnums1
is not a subset of anynums2
(ignoring wheni == j
, which is self-comparison), it is considered unique.
- Iterating over every set (
-
Result Construction: If a set is found to be unique, the index of that set (representing the person) is added to the answer list,
ans
. This is the list of integers to be returned. -
Returning the Output: Return the answer list,
ans
, which contains the indices of persons with unique favorite companies lists in increasing order.
The Python code provided uses the built-in set data structure, which is highly optimized for operations like union, intersection, and difference. This approach is efficient both in terms of time and space complexity. The critical optimization here is the usage of the set difference operation to quickly check if one set is a subset of another, thereby eliminating the need for a more cumbersome element-by-element comparison.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach with the following array of favorite companies for 3 different people:
favoriteCompanies = [ ["Apple", "Google"], // Person 0 ["Google", "Amazon"], // Person 1 ["Apple", "Netflix"] // Person 2 ]
Here, we want to find out which person has a unique list of favorite companies that is not simply a subset of any other person's list of favorite companies. Now let's apply the provided solution approach to this example:
-
Hash Map Creation:
- We loop through each person's list and create a hash map of companies to unique integers:
d = {"Apple": 0, "Google": 1, "Amazon": 2, "Netflix": 3}
- The index
idx
is incremented every time we add a new company to the hash map.
- We loop through each person's list and create a hash map of companies to unique integers:
-
Conversion to Integer Sets:
- Convert the favorite companies lists into sets of integers using the hash map
d
:t = [ {0, 1}, // Person 0's companies converted to integers {1, 2}, // Person 1's companies converted to integers {0, 3} // Person 2's companies converted to integers ]
- Convert the favorite companies lists into sets of integers using the hash map
-
Unique Lists Identification:
- Now we check if any set is a subset of another set.
- For Person 0,
{0, 1}
is not a subset of{1, 2}
or{0, 3}
. - For Person 1,
{1, 2}
is not a subset of{0, 1}
or{0, 3}
. - For Person 2,
{0, 3}
is not a subset of{0, 1}
or{1, 2}
. - Therefore, each person has at least one company that is not included in any other person's list, indicating all sets are unique.
-
Result Construction:
- Since all people have unique sets of favorite companies, we add all their indices to the list
ans
:ans = [0, 1, 2]
- Since all people have unique sets of favorite companies, we add all their indices to the list
-
Returning the Output:
- The final output
ans
is already sorted in this case, so we can directly return it as the list of people with unique favorite companies:return [0, 1, 2]
- The final output
Following the above steps with our example data, we determine that each person has a unique set of favorite companies. The corresponding Python code would identify all individuals in favoriteCompanies
as having a unique list and return their indices [0, 1, 2]
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def peopleIndexes(self, favorite_companies: List[List[str]]) -> List[int]:
5 # Create a dictionary to map company names to unique index numbers.
6 company_to_index = {}
7 index_counter = 0
8
9 # Create a list to hold sets of unique company indices for each person.
10 people_company_indices = []
11
12 # Convert each person's list of favorite companies to a set of unique index numbers.
13 for companies in favorite_companies:
14 for company in companies:
15 # If company is not in the dictionary, add it with a new index.
16 if company not in company_to_index:
17 company_to_index[company] = index_counter
18 index_counter += 1
19 # Add the set of indices for the current person's favorite companies to the list.
20 people_company_indices.append({company_to_index[company] for company in companies})
21
22 # Initialize a list to hold the indexes of people with unique company lists.
23 unique_people_indexes = []
24
25 # Check each person's favorite companies against all others' to determine uniqueness.
26 for i, person_companies_indices in enumerate(people_company_indices):
27 unique = True
28 for j, other_person_companies_indices in enumerate(people_company_indices):
29 # Skip comparison with itself.
30 if i == j:
31 continue
32 # If the current person's companies are a subset of another's, set unique to false.
33 if not (person_companies_indices - other_person_companies_indices):
34 unique = False
35 break
36 # If unique is still true, add the current person's index to the result list.
37 if unique:
38 unique_people_indexes.append(i)
39
40 # Return the list of indexes of people with unique lists of favorite companies.
41 return unique_people_indexes
42
1class Solution {
2 public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
3 // Dictionary to map company names to unique indices
4 Map<String, Integer> companyIndexMap = new HashMap<>();
5 int index = 0; // Running index for assigning to companies
6 int peopleCount = favoriteCompanies.size(); // Total number of people
7 Set<Integer>[] companySets = new Set[peopleCount]; // Array of sets to hold the indices of companies
8
9 // Step 1: Assign unique index to each company and create sets of company indices per person
10 for (int i = 0; i < peopleCount; ++i) {
11 List<String> companies = favoriteCompanies.get(i); // Get the favorite companies of person i
12 // Map each company to a unique index if not already done
13 for (String company : companies) {
14 if (!companyIndexMap.containsKey(company)) {
15 companyIndexMap.put(company, index++);
16 }
17 }
18 // Create a set of indices for the person's favorite companies
19 Set<Integer> companySet = new HashSet<>();
20 for (String company : companies) {
21 companySet.add(companyIndexMap.get(company));
22 }
23 companySets[i] = companySet;
24 }
25
26 // Step 2: Find people whose list of favorite companies is not a subset of any other list
27 List<Integer> result = new ArrayList<>();
28 for (int i = 0; i < peopleCount; ++i) {
29 boolean isUnique = true;
30 // Check if there is any other person j whose favorite companies include all of i's favorite companies
31 for (int j = 0; j < peopleCount; ++j) {
32 if (i != j && companySets[j].containsAll(companySets[i])) {
33 isUnique = false; // Person i's list is not unique, as it is a subset of person j's list
34 break;
35 }
36 }
37 // If person i's list is unique, add their index to the result list
38 if (isUnique) {
39 result.add(i);
40 }
41 }
42
43 return result;
44 }
45}
46
1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <unordered_set>
5
6class Solution {
7public:
8 // Function to find the indexes of people whose list of favorite companies is not a
9 // subset of any other list of favorite companies.
10 vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
11 unordered_map<string, int> companyToIndex;
12 int index = 0;
13 int numberOfPeople = favoriteCompanies.size();
14 vector<unordered_set<int>> transformedCompanies(numberOfPeople);
15
16 // Assign an index to each company and transform the favorite companies into a set of unique indexes.
17 for (int i = 0; i < numberOfPeople; ++i) {
18 for (auto& company : favoriteCompanies[i]) {
19 if (!companyToIndex.count(company)) {
20 companyToIndex[company] = index++;
21 }
22 }
23 unordered_set<int> companyIndexes;
24 for (auto& company : favoriteCompanies[i]) {
25 companyIndexes.insert(companyToIndex[company]);
26 }
27 transformedCompanies[i] = companyIndexes;
28 }
29
30 vector<int> result;
31 // Check each person's list of companies to ensure it is not a subset of another list.
32 for (int i = 0; i < numberOfPeople; ++i) {
33 bool isSubset = false;
34 for (int j = 0; j < numberOfPeople; ++j) {
35 if (i == j) continue; // Skip comparison with the same person.
36 if (isSubsetCheck(transformedCompanies[i], transformedCompanies[j])) {
37 isSubset = true;
38 break; // The current list is a subset of another list, no need to continue checking.
39 }
40 }
41 if (!isSubset) {
42 result.push_back(i); // If the list is not a subset, include the person's index in the result.
43 }
44 }
45 return result;
46 }
47
48private:
49 // Helper function to check if set nums1 is a subset of set nums2.
50 bool isSubsetCheck(const unordered_set<int>& nums1, const unordered_set<int>& nums2) {
51 for (int value : nums1) {
52 if (!nums2.count(value)) {
53 return false; // nums1 is not a subset of nums2 since an element is missing in nums2.
54 }
55 }
56 return true; // All elements in nums1 are found in nums2; nums1 is a subset of nums2.
57 }
58};
59
1type CompanyIndexMap = { [key: string]: number };
2type CompanySet = Set<number>;
3
4// Maps a company to a unique index.
5let companyToIndex: CompanyIndexMap = {};
6// Transformed favorite companies represented as sets of unique indexes.
7let transformedCompanies: CompanySet[] = [];
8
9// Function to find the indexes of people whose list of favorite companies is not a
10// subset of any other list of favorite companies.
11function peopleIndexes(favoriteCompanies: string[][]): number[] {
12 let index = 0;
13 let numberOfPeople = favoriteCompanies.length;
14 transformedCompanies = new Array(numberOfPeople);
15
16 // Assign an index to each company and transform the favorite companies into a set of unique indexes.
17 for (let i = 0; i < numberOfPeople; ++i) {
18 for (const company of favoriteCompanies[i]) {
19 if (companyToIndex[company] === undefined) {
20 companyToIndex[company] = index++;
21 }
22 }
23 let companyIndexes = new Set<number>();
24 for (const company of favoriteCompanies[i]) {
25 companyIndexes.add(companyToIndex[company]);
26 }
27 transformedCompanies[i] = companyIndexes;
28 }
29
30 let result: number[] = [];
31 // Check each person's list of companies to ensure it is not a subset of another list.
32 for (let i = 0; i < numberOfPeople; ++i) {
33 let isSubset = false;
34 for (let j = 0; j < numberOfPeople; ++j) {
35 if (i === j) continue; // Skip comparison with the same person.
36 if (isSubsetCheck(transformedCompanies[i], transformedCompanies[j])) {
37 isSubset = true;
38 break; // The current list is a subset of another list, no need to continue checking.
39 }
40 }
41 if (!isSubset) {
42 result.push(i); // If the list is not a subset, include the person's index in the result.
43 }
44 }
45 return result;
46}
47
48// Helper function to check if set A is a subset of set B.
49function isSubsetCheck(setA: CompanySet, setB: CompanySet): boolean {
50 for (let value of setA) {
51 if (!setB.has(value)) {
52 return false; // Set A is not a subset of set B since an element is missing in set B.
53 }
54 }
55 return true; // All elements in set A are found in set B; set A is a subset of set B.
56}
57
Time and Space Complexity
Time Complexity
The provided code involves several nested loops and set operations, which contribute to its overall time complexity. Here's a breakdown of the main components:
-
Building the dictionary
d
:- The outer loop goes through each list of companies, and the inner loop goes through each company within a list.
- Worst case time complexity for building
d
isO(M*N)
, whereN
is the number of lists infavoriteCompanies
, andM
is the average number of companies in each list.
-
Constructing the set
t
:- This part also involves an outer loop through each list and an inner loop through each company.
- The construction of sets is
O(M)
per list, leading toO(M*N)
time complexity for this step.
-
The comparison loops to determine if one set is a subset of another:
- There are two nested loops, each going through the
N
sets. - For each pair of sets, the subset check operation involves a difference operation which can take up to
O(M)
in the worst case. - Therefore, this part has
O(N^2 * M)
time complexity.
- There are two nested loops, each going through the
Combining all these, the overall time complexity is dominated by the subset check, giving O(N^2 * M)
.
Space Complexity
The space complexity consists of the storage for the dictionary d
, the list of sets t
, and the answer list ans
:
-
The dictionary
d
has a space complexity ofO(U)
, whereU
is the total number of unique companies across all lists. -
The list of sets
t
stores each company as an integer index, so each set takesO(M)
space, and forN
lists, this isO(M*N)
space. -
The answers list
ans
can contain at mostN
elements, which givesO(N)
.
Given that U
may be less than M*N
(since some companies could be repeated), the overall space complexity is O(M*N)
due to storing sets corresponding to the list of lists favoriteCompanies
.
Learn more about how to find time and space complexity quickly using problem constraints.
How many times is a tree node visited in a depth first search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!