1452

1452. People Whose List of Favorite Companies Is Not a Subset of Another List (Medium)

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.

Companies:
Google

Related Topics:
Array, Hash Table, String

Solution 1. Two Pointers

For A[i], check if it's a subset of A[j] (0 <= j < N and j != i). For the check method isSubset, we can use two pointers.

// OJ: https://leetcode.com/problems/people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list/
// Author: github.com/lzl124631x
// Time: O(NMlogM + N^2 * MW)  where `N` is the length of `A`, `M` is the maximum length of `A[i]`, and `W` is the maximum length of a company name.
// Space: O(N)
class Solution {
public:
    vector<int> peopleIndexes(vector<vector<string>>& A) {
        int N = A.size();
        for (auto &v : A) sort(begin(v), end(v));
        vector<int> sub(N), ans; // sub[i] = 1 if A[i] is a subset of another element. Otherwise = 0
        auto isSubset = [&](int i, int j) {
            auto &a = A[i], &b = A[j];
            if (a.size() > b.size()) return false;
            for (int p = 0, q = 0; p < a.size(); ++p) {
                while (q < b.size() && b[q] < a[p]) ++q;
                if (q == b.size() || b[q] != a[p]) return false;
                ++q;
            }
            return true;
        };
        for (int i = 0; i < N; ++i) {
            int j = 0;
            for (; j < N; ++j) {
                if (i == j || sub[j]) continue; // If we know `A[j]` is a subset of another element already, we can skip checking it. We only need to check `A[j]`'s superset element.
                if (isSubset(i, j)) {
                    sub[i] = 1;
                    break;
                }
            }
            if (j == N) ans.push_back(i);
        }
        return ans;
    }
};

To save time on string comparison, we can map strings to index IDs.

// OJ: https://leetcode.com/problems/people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list/
// Author: github.com/lzl124631x
// Time: O(NMW + NMlogM + N^2 * M) where `N` is the length of `A`, `M` is the maximum length of `A[i]`, and `W` is the maximum length of a company name.
// Space: O(NMW)
class Solution {
    bool isSubset(vector<int> &a, vector<int> &b) {
        if (a.size() > b.size()) return false;
        int M = a.size(), N = b.size(), i = 0, j = 0;
        for (; i < M; ++i) {
            while (j < N && b[j] < a[i]) ++j;
            if (j >= N || b[j] != a[i]) break;
        }
        return i == M;
    }
public:
    vector<int> peopleIndexes(vector<vector<string>>& A) {
        int id = 0;
        unordered_map<string, int> m; // name -> id
        for (auto &names : A) {
            for (auto &name : names) {
                if (m.count(name) == 0) m[name] = id++; // map company name to an ID
            }
        }
        vector<vector<int>> B;
        for (auto &names : A) {
            B.emplace_back();
            for (auto &name : names) B.back().push_back(m[name]);
            sort(begin(B.back()), end(B.back())); // Get the encoded company names in ascending order.
        }
        vector<int> ans;
        for (int i = 0; i < B.size(); ++i) {
            int j = 0;
            for (; j < B.size(); ++j) {
                if (i == j) continue;
                if (isSubset(B[i], B[j])) break;
            }
            if (j == B.size()) ans.push_back(i);
        }
        return ans;
    }
};

Or use bitmask. We need NM bits in the bitmask.

// OJ: https://leetcode.com/problems/people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list/
// Author: github.com/lzl124631x
// Time: O(N^2 * MW + N^3 * M)
// Space: O(NMW + N^2 * M)
class Solution {
public:
    vector<int> peopleIndexes(vector<vector<string>>& A) {
        int id = 0, N = A.size();
        vector<bitset<50000>> v;
        unordered_map<string, int> m; // name -> id
        for (auto &p : A) {
            bitset<50000> bs;
            for (auto &c : p) {
                if (m.count(c) == 0) m[c] = id++;
                bs.set(m[c]);
            }
            v.push_back(bs);
        }
        vector<int> ans;
        for (int i = 0; i < N; ++i) {
            int j = 0;
            for (; j < N; ++j) {
                if (i == j) continue;
                if ((v[i] | v[j]) == v[j]) break;
            }
            if (j == N) ans.push_back(i);
        }
        return ans;
    }
};