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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

    
    
    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].
    

1
2
3
4
5
6
7

    
    
    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].
    

1
2
3
4
5
6

    
    
    Input: favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]]
    Output: [0,1,2,3]
    

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
class Solution {
public:
    vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
        int n = favoriteCompanies.size();
        vector<unordered_set<string>> sets(n);
        for (int i = 0; i < n; ++i)
            sets[i] = unordered_set<string>(favoriteCompanies[i].begin(), favoriteCompanies[i].end());
        vector<int> res;
        for (int i = 0; i < n; ++i) {
            bool subset = false;
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                if (sets[i].size() > sets[j].size()) continue;
                bool is_subset = true;
                for (const auto& c : sets[i]) if (!sets[j].count(c)) { is_subset = false; break; }
                if (is_subset) { subset = true; break; }
            }
            if (!subset) res.push_back(i);
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func peopleIndexes(favoriteCompanies [][]string) []int {
    n := len(favoriteCompanies)
    sets := make([]map[string]struct{}, n)
    for i := range favoriteCompanies {
        sets[i] = make(map[string]struct{})
        for _, c := range favoriteCompanies[i] {
            sets[i][c] = struct{}{}
        }
    }
    res := []int{}
    for i := 0; i < n; i++ {
        subset := false
        for j := 0; j < n; j++ {
            if i == j || len(sets[i]) > len(sets[j]) { continue }
            isSubset := true
            for c := range sets[i] {
                if _, ok := sets[j][c]; !ok { isSubset = false; break }
            }
            if isSubset { subset = true; break }
        }
        if !subset { res = append(res, i) }
    }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

import java.util.*;
class Solution {
    public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
        int n = favoriteCompanies.size();
        List<Set<String>> sets = new ArrayList<>();
        for (List<String> fc : favoriteCompanies) sets.add(new HashSet<>(fc));
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            boolean subset = false;
            for (int j = 0; j < n; j++) {
                if (i == j || sets.get(i).size() > sets.get(j).size()) continue;
                if (sets.get(j).containsAll(sets.get(i))) { subset = true; break; }
            }
            if (!subset) res.add(i);
        }
        return res;
    }
}

1
2
3
4
5
6
7
8

class Solution {
    fun peopleIndexes(favoriteCompanies: List<List<String>>): List<Int> {
        val sets = favoriteCompanies.map { it.toSet() }
        return sets.indices.filter { i ->
            sets.indices.all { j -> i == j || sets[i].size > sets[j].size || !sets[j].containsAll(sets[i]) }
        }
    }
}

1
2
3
4
5
6
7

def peopleIndexes(favoriteCompanies: list[list[str]]) -> list[int]:
    sets = [set(fc) for fc in favoriteCompanies]
    res = []
    for i, s in enumerate(sets):
        if not any(i != j and s <= sets[j] for j in range(len(sets))):
            res.append(i)
    return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

fn people_indexes(favorite_companies: Vec<Vec<String>>) -> Vec<usize> {
    let sets: Vec<std::collections::HashSet<_>> = favorite_companies.iter().map(|fc| fc.iter().collect()).collect();
    let mut res = vec![];
    for (i, s) in sets.iter().enumerate() {
        if !sets.iter().enumerate().any(|(j, t)| i != j && s.len() <= t.len() && s.is_subset(t)) {
            res.push(i);
        }
    }
    res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

function peopleIndexes(favoriteCompanies: string[][]): number[] {
    const sets = favoriteCompanies.map(fc => new Set(fc));
    const res: number[] = [];
    for (let i = 0; i < sets.length; i++) {
        let subset = false;
        for (let j = 0; j < sets.length; j++) {
            if (i === j || sets[i].size > sets[j].size) continue;
            if ([...sets[i]].every(c => sets[j].has(c))) { subset = true; break; }
        }
        if (!subset) res.push(i);
    }
    return res;
}