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

In this Leetcode problem, we are given a list of (distinct) sets and we should return the indices (sorted) for which the sets are not subsets of other sets in the list.

Problem statement

Solution

Before giving the whole solution, let’s talk about the main ideas to solve the problem:

• First, we build Group objects which represent one set of companies. In my implementation I have a groupId to each group, but I could/should have used userIndex as id/key, instead of generating my own id.
• We want to build a reverse index from companies to the list of Group they belong to. That will allow us to check in a new set is included in any previous set.
• Set comparison: when we look at a new set of companies, we count how many common items the set has with all the other sets. If the number of common items is the number of items in an existing set, then the existing set is included in the new set. If the number of common items is the number of items in the new set, then the new set is including in an existing set
• We can add methods add and remove to add and remove new groups from the set of results, as we go through the list.