We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

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

Number: 1562

Difficulty: Medium

Paid? No

Companies: Datadog, Google

Problem Description

Given an array favoriteCompanies where favoriteCompanies[i] represents the list of favorite companies of the ith person, return the indices of people whose list is not a subset of any other person's list of favorite companies. The answer should be returned in increasing order.

Key Insights

  • Convert each person's list into a set for fast subset checking.
  • Compare every pair of people's sets to determine if one is a subset of the other.
  • Since all lists are distinct (even when sorted), no two sets will be the same.
  • Use a double loop (O(n^2)) to check for subset relationships, which is feasible given the constraint that the number of persons n is at most 100.

Space and Time Complexity

Time Complexity: O(n^2 * m) where n is the number of persons and m is the average number of companies per list (for subset checking). Space Complexity: O(n * m) for storing the sets of favorite companies.

Solution

The solution involves converting each list of companies into a set. Then, for each person, we iterate through all other persons and check if the current person's set is a subset of any other person's set using the subset operation provided by the set data structure. If the set is not a subset of any other set, add the index to the result list. Finally, sort the result list in increasing order and return it.

Code Solutions

# Define a function that takes the list of favorite companies.
def peopleIndexes(favoriteCompanies):
    # Convert each list of companies into a set for fast subset checking.
    companies_sets = [set(companies) for companies in favoriteCompanies]
    result = []
    
    # Iterate through each person's companies list.
    for i in range(len(companies_sets)):
        isSubset = False
        # Compare with every other person's companies list.
        for j in range(len(companies_sets)):
            if i != j and companies_sets[i].issubset(companies_sets[j]):
                # If current set is a subset of another, mark as subset.
                isSubset = True
                break
        if not isSubset:
            result.append(i)
    
    # The final result should be in increasing order.
    return sorted(result)

# Example use case:
favoriteCompanies = [["leetcode","google","facebook"], ["google","microsoft"], ["google","facebook"], ["google"], ["amazon"]]
print(peopleIndexes(favoriteCompanies))  # Output: [0,1,4]
← Back to All Questions