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).
1function smallestSufficientTeam(req_skills, people) {
2 const skillIndex = req_skills.reduce((acc, skill, i) => (acc[skill] = i, acc), {});
3 const n = req_skills.length;
4 let dp = {0: []};
5
6 people.forEach((p, i) => {
7 let hisSkill = 0;
8 p.forEach(skill => {
9 if (skill in skillIndex) {
10 hisSkill |= 1 << skillIndex[skill];
11 }
12 });
13 const newDp = { ...dp };
14 for (const [skillSet, team] of Object.entries(dp)) {
15 const withHim = skillSet | hisSkill;
16 if (newDp[withHim] === undefined || newDp[withHim].length > team.length + 1) {
17 newDp[withHim] = [...team, i];
18 }
19 }
20 dp = newDp;
21 });
22
23 return dp[(1 << n) - 1];
24}The JavaScript solution employs a similar strategy using an object structure to keep track of the smallest team covering each set of skills, denoted as bitmasks. It iterates over each person, computes the bitmask for their skills, and updates possible combinations of team skills within the dynamic programming object dp.
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.
1import java.util.*;
2
3
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.
This Java implementation uses recursion to explore the assembly of teams in a backtracking manner. We map each skill to a bit index, then convert each person's skills to a bitmask. We recursively decide whether to include each person in the current team, pruning branches that exceed the current smallest team's size or cannot complete the skill set. The smallest sufficient team is stored in bestTeam.