#1452
People Whose List of Favorite Companies Is Not a Subset of Another List
MediumArrayHash TableStringHash MapArray
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n * m) |
| Space | O(1) | O(n) |
💡
Intuition
Time O(n * m)Space O(n)
We can use a hashing technique to represent each person's favorite companies as a bitmask, allowing us to efficiently check for subsets using bitwise operations.
⚙️
Algorithm
3 steps- 1Step 1: Create a mapping of company names to unique integers.
- 2Step 2: Convert each person's list of favorite companies into a bitmask using the mapping.
- 3Step 3: Compare each person's bitmask with every other person's bitmask to check for subsets using bitwise AND operations.
solution.py21 lines
1def peopleIndexes(favoriteCompanies):
2 company_map = {}
3 bitmasks = []
4 for companies in favoriteCompanies:
5 bitmask = 0
6 for company in companies:
7 if company not in company_map:
8 company_map[company] = len(company_map)
9 bitmask |= 1 << company_map[company]
10 bitmasks.append(bitmask)
11
12 result = []
13 for i in range(len(bitmasks)):
14 is_subset = False
15 for j in range(len(bitmasks)):
16 if i != j and (bitmasks[i] & bitmasks[j]) == bitmasks[i]:
17 is_subset = True
18 break
19 if not is_subset:
20 result.append(i)
21 return resultℹ
Complexity note: The time complexity is O(n * m) where n is the number of people and m is the average number of companies per person. The space complexity is O(n) due to the storage of the bitmasks.
- 1Understanding subsets is crucial for this problem.
- 2Using bitmasks can significantly optimize subset checks.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.