Leetcode 1452: People Whose List of Favorite Companies Is Not a Subset of Another List
Given an array of lists where
favoriteCompanies[i] represents the favorite companies of the i-th person, find the indices of people whose favorite company lists are not subsets of any other person’s list. Return these indices in increasing order.Problem
Approach
Steps
Complexity
Input: The input is a 2D array where each element is a list of strings representing the favorite companies of a person.
Example: Input: favoriteCompanies = [["apple","google","amazon"],["apple","microsoft"],["google","apple"],["amazon"]]
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 are distinct.
• Strings consist of lowercase English letters only.
Output: Return a list of indices of people whose favorite companies are not subsets of any other list, in increasing order.
Example: Output: [0,1,3]
Constraints:
• The output indices must be in sorted order.
• If a person's list is not a subset of any other, their index must be included.
Goal: Identify all people whose favorite company lists are unique and not subsets of other people's lists.
Steps:
• Sort each person's favorite company list for efficient subset checking.
• For each person, compare their list with all other people's lists.
• If their list is not a subset of any other list, mark their index for inclusion.
• Return all such indices in increasing order.
Goal: Conditions that must be met for the input and output.
Steps:
• Each list in the input contains only distinct company names.
• Two different lists are guaranteed to be distinct even if sorted.
• Indices in the output must be sorted in ascending order.
Assumptions:
• The input lists are valid and adhere to the constraints.
• Subset checking is performed using sorted lists for efficiency.
• Input: Input: favoriteCompanies = [["apple","google"],["apple","microsoft"],["google"],["amazon"]]
• Explanation: Output: [0,1,3]. Person at index 2 has a list ["google"] which is a subset of ["apple","google"]. Others are unique.
• Input: Input: favoriteCompanies = [["facebook","instagram"],["instagram"],["twitter"],["facebook"]]
• Explanation: Output: [0,2,3]. The list at index 1 is a subset of the list at index 0.
• Input: Input: favoriteCompanies = [["youtube"],["netflix"],["amazon"],["hulu"]]
• Explanation: Output: [0,1,2,3]. All lists are unique and not subsets of one another.
Approach: Use a combination of sorting and subset checking to identify non-subset lists efficiently.
Observations:
• The problem revolves around subset checking between lists.
• Sorting each list ensures that the subset check can be efficiently done.
• Direct comparisons between every pair of lists may lead to a quadratic time complexity.
• Sort lists and use an efficient comparison method to minimize redundant checks.
Steps:
• Sort each list in the input array alphabetically for efficient subset comparison.
• Iterate over all pairs of lists to determine if one is a subset of the other.
• If a list is not a subset of any other list, add its index to the result.
• Sort the result indices in ascending order before returning.
Empty Inputs:
• Input: favoriteCompanies = [] -> Output: []. No input leads to an empty output.
Large Inputs:
• Input: A list with 100 people each having 500 companies -> Verify performance.
Special Values:
• Input: favoriteCompanies = [["a"],["a","b"],["b"]] -> Handle minimal string sizes and subsets correctly.
• Input: favoriteCompanies = [["apple"]] -> Single list remains unchanged.
Constraints:
• Handle cases where lists are identical after sorting but are not subsets.
vector<int> peopleIndexes(vector<vector<string>>& comp) {
int n = comp.size();
for(auto &c : comp)
sort(c.begin(), c.end());
vector<int> res;
for(int i = 0; i < n; i++) {
int notSubset = true;
for(int j = 0; j < n && notSubset; j++) {
if(i == j) continue;
notSubset = !includes(comp[j].begin(), comp[j].end(), comp[i].begin(), comp[i].end());
}
if(notSubset)
res.push_back(i);
}
return res;
}
1 : Function Declaration
vector<int> peopleIndexes(vector<vector<string>>& comp) {
The function 'peopleIndexes' is declared, which takes a reference to a vector of vector of strings ('comp') and returns a vector of integers.
2 : Variable Initialization
int n = comp.size();
The variable 'n' is initialized to the size of the input vector 'comp', which represents the number of elements in the input.
3 : Loop
for(auto &c : comp)
A loop is started to iterate over each vector 'c' inside the vector of vectors 'comp'.
4 : Sorting
sort(c.begin(), c.end());
The current vector 'c' is sorted in lexicographical order using the sort function.
5 : Variable Initialization
vector<int> res;
An empty vector 'res' is initialized to store the result indices of vectors that are not subsets of any other vectors.
6 : Loop
for(int i = 0; i < n; i++) {
A loop is started to iterate through each vector in 'comp' by index 'i'.
7 : Variable Initialization
int notSubset = true;
The variable 'notSubset' is initialized to true, which will be used to track whether the current vector is a subset of any other vector.
8 : Loop
for(int j = 0; j < n && notSubset; j++) {
A nested loop starts to iterate through all other vectors in 'comp' by index 'j'. The 'notSubset' flag ensures that the loop stops once a subset is found.
9 : Conditional Check
if(i == j) continue;
If the indices 'i' and 'j' are the same (i.e., comparing the same vector with itself), the loop skips to the next iteration.
10 : Subset Check
notSubset = !includes(comp[j].begin(), comp[j].end(), comp[i].begin(), comp[i].end());
The 'notSubset' flag is updated by checking if vector 'comp[i]' is included in vector 'comp[j]'. If it is, 'notSubset' is set to false.
11 : Conditional Check
if(notSubset)
If the 'notSubset' flag is still true after checking all other vectors, it means 'comp[i]' is not a subset of any other vector.
12 : Vector Update
res.push_back(i);
If 'comp[i]' is not a subset of any other vector, the index 'i' is added to the result vector 'res'.
13 : Return Statement
return res;
The function returns the vector 'res', which contains the indices of vectors that are not subsets of any other vectors.
Best Case: O(n^2 * m)
Average Case: O(n^2 * m)
Worst Case: O(n^2 * m)
Description: Where n is the number of people and m is the average length of their favorite companies list. Sorting and subset checks dominate the complexity.
Best Case: O(1)
Worst Case: O(n * m)
Description: Space is used for storing the sorted lists and the result indices.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus