1562. People Whose List Of Favorite Companies Is Not A Subset Of Another List¶

LeetCode Problem View on GitHub

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

Solution¶

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;

class Solution {
    public List<Integer> peopleIndexes(List<List<String >> favoriteCompanies) {
        int n = favoriteCompanies.size();
        List<Integer> res = new ArrayList<>();
        HashMap<Integer, ArrayList<String >> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (String s : favoriteCompanies.get(i)) {
                if (!map.containsKey(i))
                    map.put(i, new ArrayList<>());
                map.get(i).add(s);
            }
        }
        for (Map.Entry<Integer, ArrayList<String >> entry : map.entrySet()) {
            int key = entry.getKey();
            ArrayList<String> currentCmp = entry.getValue();
            boolean flag = true;
            for (Map.Entry<Integer, ArrayList<String >> otherEntry : map.entrySet()) {
                if (key == otherEntry.getKey())
                    continue;
                ArrayList<String> otherCmp = otherEntry.getValue();
                HashSet<String> set = new HashSet<>(otherCmp);
                boolean containsAll = true;
                for (String x : currentCmp) {
                    if (!set.contains(x)) {
                        containsAll = false;
                        break;
                    }
                }
                if (containsAll) {
                    flag = false;
                    break;
                }
            }
            if (flag == true) {
                res.add(key);
            }
        }
        Collections.sort(res);
        return res;
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here