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
favoriteCompanies[i]
are distinct.favoriteCompanies[i] != favoriteCompanies[j].
class Solution {
fun peopleIndexes(favoriteCompanies: List<List<String>?>): List<Int> {
val n = favoriteCompanies.size
val res: MutableList<Int> = ArrayList()
val `in`: MutableList<Set<String>> = ArrayList()
for (list in favoriteCompanies) {
`in`.add(HashSet(list))
}
outer@ for (i in 0 until n) {
for (j in res) {
if (isSubset(`in`[i], `in`[j])) {
continue@outer
}
}
for (j in i + 1 until n) {
if (isSubset(`in`[i], `in`[j])) {
continue@outer
}
}
res.add(i)
}
return res
}
private fun isSubset(subset: Set<String>, set: Set<String>): Boolean {
return if (subset.size >= set.size) {
false
} else set.containsAll(subset)
}
}