Scale Engineer

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

Med
#1342Time: O(N^2 * M * L), where N is the number of people, M is the maximum number of companies, and L is the maximum length of a company name. The N^2 factor comes from the nested loops. The M*L factor comes from the `containsAll` operation on sets of strings, which involves hashing and comparing M strings of average length L.Space: O(N * M * L), where N is the number of people, M is the maximum number of companies for a person, and L is the maximum length of a company name. This space is required to store the hash sets of company names.1 company
Data structures
ArrayHash TableString
Companies
Datadog

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. We iterate through every pair of people (i, j) and check if the favorite company list of person i is a subset of person j's list. To make the subset check efficient, we convert the lists of companies into Hash Sets, which provide average O(1) time for containment checks.

Algorithm

  • Initialize an empty list result to store the final indices.
  • Convert each person's list of favorite companies from a List<String> to a HashSet<String>. This allows for faster lookups when checking for subsets. Store these sets in a new list, say companySets.
  • Iterate through each person i from 0 to n-1 (where n is the total number of people).
  • For each person i, assume their list is not a subset of any other. Use a boolean flag, isSubset, initialized to false.
  • Start a nested loop to compare person i with every other person j.
  • If i and j are the same, skip the comparison.
  • A crucial optimization: if the size of i's company set is greater than or equal to the size of j's set, i's list cannot be a proper subset of j's list. Skip the detailed check in this case.
  • Perform the subset check: companySets.get(j).containsAll(companySets.get(i)). This checks if every company in i's set is present in j's set.
  • If i's set is a subset of j's set, set isSubset = true and break out of the inner loop (over j), as we've confirmed person i's list is a subset.
  • After the inner loop completes, if isSubset is still false, it means no other list contains all of person i's favorite companies. Add the index i to the result list.
  • After iterating through all people, return the result list.

Walkthrough

The core idea is to perform a pairwise comparison among all the lists of favorite companies. For each person's list, we check if it's a subset of any other person's list.

To implement the subset check efficiently, we first convert each List<String> of companies into a HashSet<String>. This data structure is ideal for checking the presence of an element quickly.

The algorithm proceeds as follows:

  1. Create a list of HashSet<String> from the input favoriteCompanies.
  2. Iterate through each person i.
  3. For each i, iterate through all other people j.
  4. If list[i] is a subset of list[j], we mark i as a subset and move to the next person.
  5. If we finish checking all j for a given i and haven't found it to be a subset of any other list, we add i to our result.
import java.util.*; class Solution {    public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {        int n = favoriteCompanies.size();        List<Set<String>> companySets = new ArrayList<>();        for (List<String> companies : favoriteCompanies) {            companySets.add(new HashSet<>(companies));        }         List<Integer> result = new ArrayList<>();        for (int i = 0; i < n; i++) {            boolean isSubset = false;            for (int j = 0; j < n; j++) {                if (i == j) {                    continue;                }                // A list can only be a proper subset of a larger list.                if (companySets.get(i).size() >= companySets.get(j).size()) {                    continue;                }                // Check if set i is a subset of set j                if (companySets.get(j).containsAll(companySets.get(i))) {                    isSubset = true;                    break;                }            }            if (!isSubset) {                result.add(i);            }        }        return result;    }}

Complexity

Time

O(N^2 * M * L), where N is the number of people, M is the maximum number of companies, and L is the maximum length of a company name. The N^2 factor comes from the nested loops. The M*L factor comes from the `containsAll` operation on sets of strings, which involves hashing and comparing M strings of average length L.

Space

O(N * M * L), where N is the number of people, M is the maximum number of companies for a person, and L is the maximum length of a company name. This space is required to store the hash sets of company names.

Trade-offs

Pros

  • Relatively simple to understand and implement.

  • Directly follows the logic of the problem description.

Cons

  • The time complexity is high due to repeated string hashing and comparisons within the nested loops.

  • It may result in a 'Time Limit Exceeded' (TLE) error on platforms with strict time limits, especially for larger inputs.

Solutions

class Solution { public List < Integer > peopleIndexes ( List < List < String >> favoriteCompanies ) { Map < String , Integer > d = new HashMap <>(); int idx = 0 ; int n = favoriteCompanies . size (); Set < Integer >[] t = new Set [ n ]; for ( int i = 0 ; i < n ; ++ i ) { var v = favoriteCompanies . get ( i ); for ( var c : v ) { if (! d . containsKey ( c )) { d . put ( c , idx ++); } } Set < Integer > s = new HashSet <>(); for ( var c : v ) { s . add ( d . get ( c )); } t [ i ] = s ; } List < Integer > ans = new ArrayList <>(); for ( int i = 0 ; i < n ; ++ i ) { boolean ok = true ; for ( int j = 0 ; j < n ; ++ j ) { if ( i != j ) { if ( t [ j ]. containsAll ( t [ i ])) { ok = false ; break ; } } } if ( ok ) { ans . add ( i ); } } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem