Description
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 <= 1001 <= favoriteCompanies[i].length <= 5001 <= 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.
Solutions
Solution 1: Hash Table
We can map each company to a unique integer. Then, for each person, we convert their favorite companies into a set of integers. Finally, we check if the favorite companies of one person are a subset of another person's favorite companies.
The time complexity is (n × m × k + n2 × m), and the space complexity is O(n × m). Here, n and m are the lengths of favoriteCompanies and the average length of each company's list, respectively, and k is the average length of each company.
PythonJavaC++GoTypeScript
class Solution:
def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
idx = 0
d = {}
n = len(favoriteCompanies)
nums = [set() for _ in range(n)]
for i, ss in enumerate(favoriteCompanies):
for s in ss:
if s not in d:
d[s] = idx
idx += 1
nums[i].add(d[s])
ans = []
for i in range(n):
if not any(i != j and (nums[i] & nums[j]) == nums[i] for j in range(n)):
ans.append(i)
return ans(code-box)
class Solution {
public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
int n = favoriteCompanies.size();
Map<String, Integer> d = new HashMap<>();
int idx = 0;
Set<Integer>[] nums = new Set[n];
Arrays.setAll(nums, i -> new HashSet<>());
for (int i = 0; i < n; ++i) {
var ss = favoriteCompanies.get(i);
for (var s : ss) {
if (!d.containsKey(s)) {
d.put(s, idx++);
}
nums[i].add(d.get(s));
}
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < n; ++i) {
boolean ok = true;
for (int j = 0; j < n && ok; ++j) {
if (i != j && nums[j].containsAll(nums[i])) {
ok = false;
}
}
if (ok) {
ans.add(i);
}
}
return ans;
}
}(code-box)
class Solution {
public:
vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
int n = favoriteCompanies.size();
unordered_map<string, int> d;
int idx = 0;
vector<unordered_set<int>> nums(n);
for (int i = 0; i < n; ++i) {
for (const auto& s : favoriteCompanies[i]) {
if (!d.contains(s)) {
d[s] = idx++;
}
nums[i].insert(d[s]);
}
}
auto check = [](const unordered_set<int>& a, const unordered_set<int>& b) {
for (int x : a) {
if (!b.contains(x)) {
return false;
}
}
return true;
};
vector<int> ans;
for (int i = 0; i < n; ++i) {
bool ok = true;
for (int j = 0; j < n && ok; ++j) {
if (i != j && check(nums[i], nums[j])) {
ok = false;
}
}
if (ok) {
ans.push_back(i);
}
}
return ans;
}
};(code-box)
func peopleIndexes(favoriteCompanies [][]string) (ans []int) {
n := len(favoriteCompanies)
d := make(map[string]int)
idx := 0
nums := make([]map[int]struct{}, n)
for i := 0; i < n; i++ {
nums[i] = make(map[int]struct{})
for _, s := range favoriteCompanies[i] {
if _, ok := d[s]; !ok {
d[s] = idx
idx++
}
nums[i][d[s]] = struct{}{}
}
}
check := func(a, b map[int]struct{}) bool {
for x := range a {
if _, ok := b[x]; !ok {
return false
}
}
return true
}
for i := 0; i < n; i++ {
ok := true
for j := 0; j < n && ok; j++ {
if i != j && check(nums[i], nums[j]) {
ok = false
}
}
if ok {
ans = append(ans, i)
}
}
return
}(code-box)
function peopleIndexes(favoriteCompanies: string[][]): number[] {
const n = favoriteCompanies.length;
const d: Map<string, number> = new Map();
let idx = 0;
const nums: Set<number>[] = Array.from({ length: n }, () => new Set<number>());
for (let i = 0; i < n; i++) {
for (const s of favoriteCompanies[i]) {
if (!d.has(s)) {
d.set(s, idx++);
}
nums[i].add(d.get(s)!);
}
}
const check = (a: Set<number>, b: Set<number>): boolean => {
for (const x of a) {
if (!b.has(x)) {
return false;
}
}
return true;
};
const ans: number[] = [];
for (let i = 0; i < n; i++) {
let ok = true;
for (let j = 0; j < n && ok; j++) {
if (i !== j && check(nums[i], nums[j])) {
ok = false;
}
}
if (ok) {
ans.push(i);
}
}
return ans;
}(code-box)
