300 Medium LC Problems

This is my 300th Medium LC Problem solved: https://leetcode.com/problems/people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list/

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.

Accepted

8,999

Submissions

17,331

You can just literally follow the steps shown in the problem description. It helps if you cache the elements using a hash table for quick(er) access. Not super fast, but given the reasonably small constraints, it works. Cheers, ACC.

public class Solution

{

    public IList<int> PeopleIndexes(IList<IList<string>> favoriteCompanies)

    {

        List<int> retVal = new List<int>();

        Hashtable[] cache = new Hashtable[favoriteCompanies.Count];

        for (int i = 0; i < favoriteCompanies.Count; i++)

        {

            cache[i] = new Hashtable();

            foreach (string s in favoriteCompanies[i]) cache[i].Add(s, true);

        }

        for (int i = 0; i < favoriteCompanies.Count; i++)

        {

            bool found = true;

            for (int j = 0; j < favoriteCompanies.Count; j++)

            {

                if (i != j && favoriteCompanies[j].Count >= favoriteCompanies[i].Count)

                {

                    bool subset = true;

                    foreach (string s in favoriteCompanies[i])

                    {

                        if (!cache[j].ContainsKey(s))

                        {

                            subset = false;

                            break;

                        }

                    }

                    if (subset)

                    {

                        found = false;

                        break;

                    }

                }

            }

            if (found)

            {

                retVal.Add(i);

            }

        }

        return retVal;

    }

}