People Whose List of Favorite Companies Is Not a Subset of Another List
MediumUpdated: Oct 13, 2025
Practice on:
Problem
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 asubset of any other list of favorites companies. You must return the indices in increasing order.
Examples
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 <= 1001 <= favoriteCompanies[i].length <= 5001 <= 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
Method 1 - Set Comparison (Pairwise Subset Check)
Intuition
For each person, check if their list is a subset of any other person's list. If not, include their index in the answer.
Approach
Convert each list to a set. For each person i, check all other persons j ≠ i. If set i is a subset of set j, skip i. Otherwise, include i in the result.
Code
C++
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
class Solution {
public:
vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
int n = favoriteCompanies.size();
vector<unordered_set<string>> sets(n);
for (int i = 0; i < n; ++i)
sets[i] = unordered_set<string>(favoriteCompanies[i].begin(), favoriteCompanies[i].end());
vector<int> res;
for (int i = 0; i < n; ++i) {
bool subset = false;
for (int j = 0; j < n; ++j) {
if (i == j) continue;
if (sets[i].size() > sets[j].size()) continue;
bool is_subset = true;
for (const auto& c : sets[i]) if (!sets[j].count(c)) { is_subset = false; break; }
if (is_subset) { subset = true; break; }
}
if (!subset) res.push_back(i);
}
return res;
}
};
Go
func peopleIndexes(favoriteCompanies [][]string) []int {
n := len(favoriteCompanies)
sets := make([]map[string]struct{}, n)
for i := range favoriteCompanies {
sets[i] = make(map[string]struct{})
for _, c := range favoriteCompanies[i] {
sets[i][c] = struct{}{}
}
}
res := []int{}
for i := 0; i < n; i++ {
subset := false
for j := 0; j < n; j++ {
if i == j || len(sets[i]) > len(sets[j]) { continue }
isSubset := true
for c := range sets[i] {
if _, ok := sets[j][c]; !ok { isSubset = false; break }
}
if isSubset { subset = true; break }
}
if !subset { res = append(res, i) }
}
return res
}
Java
import java.util.*;
class Solution {
public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
int n = favoriteCompanies.size();
List<Set<String>> sets = new ArrayList<>();
for (List<String> fc : favoriteCompanies) sets.add(new HashSet<>(fc));
List<Integer> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
boolean subset = false;
for (int j = 0; j < n; j++) {
if (i == j || sets.get(i).size() > sets.get(j).size()) continue;
if (sets.get(j).containsAll(sets.get(i))) { subset = true; break; }
}
if (!subset) res.add(i);
}
return res;
}
}
Kotlin
class Solution {
fun peopleIndexes(favoriteCompanies: List<List<String>>): List<Int> {
val sets = favoriteCompanies.map { it.toSet() }
return sets.indices.filter { i ->
sets.indices.all { j -> i == j || sets[i].size > sets[j].size || !sets[j].containsAll(sets[i]) }
}
}
}
Python
def peopleIndexes(favoriteCompanies: list[list[str]]) -> list[int]:
sets = [set(fc) for fc in favoriteCompanies]
res = []
for i, s in enumerate(sets):
if not any(i != j and s <= sets[j] for j in range(len(sets))):
res.append(i)
return res
Rust
fn people_indexes(favorite_companies: Vec<Vec<String>>) -> Vec<usize> {
let sets: Vec<std::collections::HashSet<_>> = favorite_companies.iter().map(|fc| fc.iter().collect()).collect();
let mut res = vec![];
for (i, s) in sets.iter().enumerate() {
if !sets.iter().enumerate().any(|(j, t)| i != j && s.len() <= t.len() && s.is_subset(t)) {
res.push(i);
}
}
res
}
TypeScript
function peopleIndexes(favoriteCompanies: string[][]): number[] {
const sets = favoriteCompanies.map(fc => new Set(fc));
const res: number[] = [];
for (let i = 0; i < sets.length; i++) {
let subset = false;
for (let j = 0; j < sets.length; j++) {
if (i === j || sets[i].size > sets[j].size) continue;
if ([...sets[i]].every(c => sets[j].has(c))) { subset = true; break; }
}
if (!subset) res.push(i);
}
return res;
}
Complexity
- ⏰ Time complexity:
O(n^2 * m)where n is the number of people and m is the average list size - 🧺 Space complexity:
O(n * m)