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.
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 <= 161 <= req_skills[i].length <= 16req_skills[i] consists of lowercase English letters.req_skills are unique.1 <= people.length <= 600 <= people[i].length <= 161 <= people[i][j].length <= 16people[i][j] consists of lowercase English letters.people[i] are unique.people[i] is a skill in req_skills.Smallest Sufficient Team can be solved efficiently using bitmasking combined with dynamic programming. Each required skill is mapped to a unique bit position, allowing the complete skill set to be represented as a bitmask. Similarly, every person’s skills are converted into a bitmask representing the skills they contribute.
The core idea is to maintain a DP map where dp[mask] stores the smallest team capable of achieving the skill set represented by that mask. For each person, combine their skill mask with existing states and update the DP state if a smaller team is found. This incremental process gradually builds all possible skill combinations while always keeping the minimal team.
This approach avoids brute-force team enumeration and leverages efficient bit operations for merging skill sets. With careful state updates and pruning, the algorithm efficiently finds the minimal team covering all required skills.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bitmask Dynamic Programming | O(n * 2^m) | O(2^m) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Do a bitmask DP.
For each person, for each set of skills, we can update our understanding of a minimum set of people needed to perform this set of skills.
This approach leverages a bitmask along with dynamic programming to solve the problem of finding the smallest sufficient team. We use a bitmask to represent the combination of skills possessed by a team. Dynamic programming is employed to track the smallest team for every possible combination of skills, allowing us to build up to a team that covers all required skills.
Time Complexity: O(people.length * 2^n), where n is the number of required skills. Space Complexity: O(2^n).
1def smallest_sufficient_team(req_skills, people):
2 skill_index = {skill: i for i, skill in enumerate(req_skills)}
3 n = len(req_skills)
4 dp = {0: []}
5
6 for i, p in enumerate(people):
7 his_skill = 0
8 for skill in p:
9 if skill in skill_index:
10 his_skill |= 1 << skill_index[skill]
11 new_dp = dp.copy()
12 for skill_set, team in dp.items():
13 with_him = skill_set | his_skill
14 if with_him == skill_set:
15 continue
16 if with_him not in new_dp or len(new_dp[with_him]) > len(team) + 1:
17 new_dp[with_him] = team + [i]
18 dp = new_dp
19
20 return dp[(1 << n) - 1]The code utilizes a dictionary, skill_index, to map each skill to a unique index. We then define a dynamic programming dictionary, dp, where each key represents a set of skills (using bitmask), and value is the team of indices representing people with these skills.
For each person, we calculate the his_skill bitmask, which marks the skills this person can cover. We iterate over each entry in our dynamic programming table, updating it with the new combinations of skills that could be formed by adding the current person.
The result is found in dp[(1 << n) - 1], where n is the length of req_skills, representing the full set of skills covered.
This approach utilizes backtracking to explore all possible combinations of people in attempting to form the smallest team covering all required skills. We prune branches once we find a valid team, retaining the best (smallest) solution observed so far.
Time Complexity: O(2^people.length), worst case exploring all combinations. Space Complexity: O(people.length) due to recursive depth.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 int minSize = int.MaxValue;
6 List<int> bestTeam = new List<int>();
public int[] SmallestSufficientTeam(string[] req_skills, IList<IList<string>> people) {
var skillIndex = new Dictionary<string, int>();
for (int i = 0; i < req_skills.Length; ++i) {
skillIndex[req_skills[i]] = i;
}
int[] peopleSkills = new int[people.Count];
for (int i = 0; i < people.Count; ++i) {
foreach (var skill in people[i]) {
if (skillIndex.ContainsKey(skill))
peopleSkills[i] |= 1 << skillIndex[skill];
}
}
Backtrack(peopleSkills, 0, new List<int>(), 0, (1 << req_skills.Length) - 1);
return bestTeam.ToArray();
}
private void Backtrack(int[] peopleSkills, int index, List<int> currentTeam, int currentSkills, int fullSkills) {
if (currentSkills == fullSkills) {
if (currentTeam.Count < minSize) {
minSize = currentTeam.Count;
bestTeam = new List<int>(currentTeam);
}
return;
}
if (index == peopleSkills.Length || currentTeam.Count >= minSize) {
return;
}
Backtrack(peopleSkills, index + 1, currentTeam, currentSkills, fullSkills);
currentTeam.Add(index);
Backtrack(peopleSkills, index + 1, currentTeam, currentSkills | peopleSkills[index], fullSkills);
currentTeam.RemoveAt(currentTeam.Count - 1);
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Bitmasking efficiently represents skill sets as integers, allowing quick combination of skills using bitwise OR operations. This representation drastically reduces complexity compared to handling skill sets with lists or sets.
Yes, this problem reflects common FAANG interview themes such as bitmasking, dynamic programming, and state optimization. It tests a candidate’s ability to model combinational states and optimize search space efficiently.
The optimal approach uses bitmasking combined with dynamic programming. Each skill is represented as a bit, and DP states track the smallest team capable of forming each skill combination. This allows efficient merging of skills while always keeping the minimal team size.
A hash map or array-based DP structure indexed by bitmasks works best. It stores the smallest team corresponding to each skill combination. Bit manipulation enables fast merging of skill sets and efficient state transitions.
The C# solution uses a similar backtracking method. It computes the state by converting skills into a bitmask and recurses by selectively adding people to the team. When a complete team is found that covers all required skills, it checks if it's the smallest seen so far. Branches are pruned if they're suboptimal by current measurement.