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.
Solution: Hashtable
Time complexity: O(n*n*m)
Space complexity: O(n*m)
where n is the # of people, m is the # of companies
C++
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 27 28 29 30 |
// Author: Huahua, 664 ms 58.4 MB class Solution { public: vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) { const int n = favoriteCompanies.size(); vector<unordered_set<string>> m; for (const auto& c : favoriteCompanies) m.emplace_back(begin(c), end(c)); vector<int> ans; for (int i = 0; i < n; ++i) { bool valid = true; for (int j = 0; j < n && valid; ++j) { if (i == j) continue; bool subset = true; for (const auto& s : m[i]) if (!m[j].count(s)) { subset = false; break; } if (subset) { valid = false; break; } } if (valid) ans.push_back(i); } return ans; } }; |
Use int as key to make it faster.
C++
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 27 28 29 30 31 32 33 34 35 36 |
// Author: Huahua, 476 ms, 48.7 MB class Solution { public: vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) { const int n = favoriteCompanies.size(); unordered_map<string, int> ids; vector<unordered_set<int>> m; for (const auto& companies : favoriteCompanies) { m.push_back({}); for (const auto& c : companies) { if (!ids.count(c)) ids[c] = ids.size(); m.back().insert(ids[c]); } } vector<int> ans; for (int i = 0; i < n; ++i) { bool valid = true; for (int j = 0; j < n && valid; ++j) { if (i == j) continue; bool subset = true; for (const auto& s : m[i]) if (!m[j].count(s)) { subset = false; break; } if (subset) { valid = false; break; } } if (valid) ans.push_back(i); } return ans; } }; |