Welcome to Subscribe On Youtube

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

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

Solutions

  • class Solution {
    public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
        Map<String, Integer> d = new HashMap<>();
        int idx = 0;
        int n = favoriteCompanies.size();
        Set<Integer>[] t = new Set[n];
        for (int i = 0; i < n; ++i) {
            var v = favoriteCompanies.get(i);
            for (var c : v) {
                if (!d.containsKey(c)) {
                    d.put(c, idx++);
                }
            }
            Set<Integer> s = new HashSet<>();
            for (var c : v) {
                s.add(d.get(c));
            }
            t[i] = s;
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            boolean ok = true;
            for (int j = 0; j < n; ++j) {
                if (i != j) {
                    if (t[j].containsAll(t[i])) {
                        ok = false;
                        break;
                    }
                }
            }
            if (ok) {
                ans.add(i);
            }
        }
        return ans;
    }
}

  • class Solution {
public:
    vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
        unordered_map<string, int> d;
        int idx = 0, n = favoriteCompanies.size();
        vector<unordered_set<int>> t(n);
        for (int i = 0; i < n; ++i) {
            auto v = favoriteCompanies[i];
            for (auto& c : v) {
                if (!d.count(c)) {
                    d[c] = idx++;
                }
            }
            unordered_set<int> s;
            for (auto& c : v) {
                s.insert(d[c]);
            }
            t[i] = s;
        }
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            bool ok = true;
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                if (check(t[i], t[j])) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                ans.push_back(i);
            }
        }
        return ans;
    }

    bool check(unordered_set<int>& nums1, unordered_set<int>& nums2) {
        for (int v : nums1) {
            if (!nums2.count(v)) {
                return false;
            }
        }
        return true;
    }
};

  • class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        d = {}
        idx = 0
        t = []
        for v in favoriteCompanies:
            for c in v:
                if c not in d:
                    d[c] = idx
                    idx += 1
            t.append({d[c] for c in v})
        ans = []
        for i, nums1 in enumerate(t):
            ok = True
            for j, nums2 in enumerate(t):
                if i == j:
                    continue
                if not (nums1 - nums2):
                    ok = False
                    break
            if ok:
                ans.append(i)
        return ans


  • func peopleIndexes(favoriteCompanies [][]string) []int {
	d := map[string]int{}
	idx, n := 0, len(favoriteCompanies)
	t := make([]map[int]bool, n)
	for i, v := range favoriteCompanies {
		for _, c := range v {
			if _, ok := d[c]; !ok {
				d[c] = idx
				idx++
			}
		}
		s := map[int]bool{}
		for _, c := range v {
			s[d[c]] = true
		}
		t[i] = s
	}
	ans := []int{}
	check := func(nums1, nums2 map[int]bool) bool {
		for v, _ := range nums1 {
			if _, ok := nums2[v]; !ok {
				return false
			}
		}
		return true
	}
	for i := 0; i < n; i++ {
		ok := true
		for j := 0; j < n; j++ {
			if i == j {
				continue
			}
			if check(t[i], t[j]) {
				ok = false
				break
			}
		}
		if ok {
			ans = append(ans, i)
		}
	}
	return ans
}

All Problems

All Solutions