People Whose List of Favorite Companies Is Not a Subset of Another List
We need to check for each person’s list of favorite companies whether it is a subset of any other person’s list of favorite companies. If it’s not a subset, you can add the index of that person to the result.
Here’s the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution:
def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
result = []
# Convert the favorite companies of each person into a set for easy subset checking
favoriteCompaniesSets = [set(fav) for fav in favoriteCompanies]
# Iterate over each person's favorite companies and check if it is a subset of any other person's favorite companies
for i, fav_i in enumerate(favoriteCompaniesSets):
is_subset = False
for j, fav_j in enumerate(favoriteCompaniesSets):
if i != j and fav_i.issubset(fav_j): # Check if fav_i is a subset of fav_j
is_subset = True
break
if not is_subset:
result.append(i)
return result
|
This code uses a set data structure to efficiently check if one list is a subset of another. It iterates through all pairs of people’s favorite companies, so the time complexity of this solution is (O(n^2 \cdot m)), where (n) is the number of people and (m) is the average length of the favorite companies list. Given the constraints, this code will execute efficiently.