In this guide, you will get 1125. Smallest Sufficient Team LeetCode Solution with the best time and space complexity. The solution to Smallest Sufficient Team problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
In a project, you have a list of required skills req_skills, and a list of people. The ith person people[i] contains a list of skills that the person has.
Consider a sufficient team: a set of people such that for every required skill in req_skills, there is at least one person in the team who has that skill. We can represent these teams by the index of each person.
For example, team = [0, 1, 3] represents the people with skills people[0], people[1], and people[3].
Return any sufficient team of the smallest possible size, represented by the index of each person. You may return the answer in any order.
It is guaranteed an answer exists.
Example 1:
Input: req_skills = [“java”,”nodejs”,”reactjs”], people = [[“java”],[“nodejs”],[“nodejs”,”reactjs”]]
Output: [0,2]
Example 2:
Input: req_skills = [“algorithms”,”math”,”java”,”reactjs”,”csharp”,”aws”], people = [[“algorithms”,”math”,”java”],[“algorithms”,”math”,”reactjs”],[“java”,”csharp”,”aws”],[“reactjs”,”csharp”],[“csharp”,”math”],[“aws”,”java”]]
Output: [1,2]
Constraints:
1 <= req_skills.length <= 16
1 <= req_skills[i].length <= 16
req_skills[i] consists of lowercase English letters.
All the strings of req_skills are unique.
1 <= people.length <= 60
0 <= people[i].length <= 16
1 <= people[i][j].length <= 16
people[i][j] consists of lowercase English letters.
All the strings of people[i] are unique.
Every skill in people[i] is a skill in req_skills.
It is guaranteed a sufficient team exists.
Time Complexity: O(p \cdot 2^n), where p = |\texttt{people}| and n = |\texttt{req_skills}|
Space Complexity: O(2^n)
1125. Smallest Sufficient Team LeetCode Solution in C++
class Solution {
public:
vector<int> smallestSufficientTeam(vector<string>& req_skills,
vector<vector<string>>& people) {
const int n = req_skills.size();
const int nSkills = 1 << n;
unordered_map<string, int> skillToId;
// dp[i] := the minimum people's indices to cover skillset of mask i
unordered_map<int, vector<int>> dp;
dp.reserve(nSkills); // Avoid rehash.
dp[0] = {};
for (int i = 0; i < n; ++i)
skillToId[req_skills[i]] = i;
auto getSkill = [&](const vector<string>& person) {
int mask = 0;
for (const string& skill : person)
if (const auto it = skillToId.find(skill); it != skillToId.cend())
mask |= 1 << it->second;
return mask;
};
for (int i = 0; i < people.size(); ++i) {
const int currSkill = getSkill(people[i]);
for (const auto& [mask, indices] : dp) {
const int newSkillSet = mask | currSkill;
if (newSkillSet == mask) // Adding people[i] doesn't increase skill set
continue;
if (!dp.contains(newSkillSet) ||
dp[newSkillSet].size() > indices.size() + 1) {
dp[newSkillSet] = indices;
dp[newSkillSet].push_back(i);
}
}
}
return dp[nSkills - 1];
}
}; /* code provided by PROGIEZ */
1125. Smallest Sufficient Team LeetCode Solution in Java
class Solution {
public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
final int n = req_skills.length;
final int nSkills = 1 << n;
Map<String, Integer> skillToId = new HashMap();
// dp[i] := the minimum people's indices to cover skillset of mask i
List<Integer>[] dp = new List[nSkills];
dp[0] = new ArrayList<>();
for (int i = 0; i < req_skills.length; ++i)
skillToId.put(req_skills[i], i);
for (int i = 0; i < people.size(); ++i) {
final int currSkill = getSkill(people.get(i), skillToId);
for (int j = 0; j < nSkills; ++j) {
if (dp[j] == null)
continue;
final int newSkillSet = currSkill | j;
if (newSkillSet == j) // Adding people[i] doesn't increase skill set
continue;
if (dp[newSkillSet] == null || dp[newSkillSet].size() > dp[j].size() + 1) {
dp[newSkillSet] = new ArrayList<>(dp[j]);
dp[newSkillSet].add(i);
}
}
}
return dp[nSkills - 1].stream().mapToInt(Integer::intValue).toArray();
}
private int getSkill(List<String> person, Map<String, Integer> skillToId) {
int mask = 0;
for (final String skill : person)
if (skillToId.containsKey(skill))
mask |= 1 << skillToId.get(skill);
return mask;
}
} // code provided by PROGIEZ
1125. Smallest Sufficient Team LeetCode Solution in Python
