People Whose List of Favorite Companies Is Not a Subset of Another List
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].
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.
class Solution {
public List<Integer> peopleIndexes(List<List<String>> list) {
HashMap<Integer, Set<String>> sets = new HashMap<>();
for (int i = 0; i < list.size(); i++) {
Set<String> temp = new HashSet<>();
for (String x : list.get(i))
temp.add(x);
sets.put(i, temp);
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
boolean contains = false;
for (int j = 0; j < list.size(); j++) {
if (i == j)
continue;
boolean in = true;
for (String x : sets.get(i)) {
if (!sets.get(j).contains(x)) {
in = false;
break;
}
}
if (in) {
contains = true;
break;
}
}
if (!contains)
ans.add(i);
}
return ans;
}
}