Leetcode 1125. Smallest Sufficient Team

Problem Explanation

The problem involves finding the smallest sufficient team from a group of people who have different skills sets required to complete a certain project. Each person can have one or more skills from the required skills set and the challenge is to select minimum number of people in such a way that all required skills for a project are covered. It is guaranteed that a sufficient team always exists.

For example, let's say we have a list of req_skills = ["java","nodejs","reactjs"]. We have a list of people as people = [["java"],["nodejs"],["nodejs","reactjs"]]. Here second person has the skill "nodejs" and "reactjs" and the third person has "java". So, the smallest team that we can form is [0,2] covering all the required skills.

Approach

The solution uses Dynamic Programming and Bit Manipulation to solve this problem. The key realization is that a set of skills can be represented using a bitmask. This is because there are at most 16 different skills. Any subset of these skills can be represented using a bitmask of 16 bits. For bitmask, each bit represents whether a given skill is present or not. The number of possible skill sets is 2^16 = 65536, which is manageable.

We then use a hashmap (dp) to store the minimum list of people for a given skill set (represented by the bitmask). We iteratively update this hashmap for each person by updating the existing minimum team lists with the current person's skills.

Python Solution

1
2python
3class Solution:
4    def smallestSufficientTeam(self, req_skills, people):
5        n = len(req_skills)
6        N = 1 << n
7        dp = [0] + [float('inf')]*N
8        team = [[] for _ in range(N)]
9        skillToId = {skill:i for i, skill in enumerate(req_skills)}
10        for j in range(len(people)):
11            person = 0
12            for skill in people[j]:
13                if skill in skillToId:
14                    person |= (1 << skillToId[skill])
15            for skillset in range(N):
16                new_skillset = skillset | person
17                if dp[new_skillset] > dp[skillset] + 1:
18                    dp[new_skillset] = dp[skillset] + 1
19                    team[new_skillset] = team[skillset] + [j]
20        return team[N-1]

C++ Solution

1
2c++
3class Solution {
4public:
5  vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
6    unordered_map<string,int> skillToId;
7    for(int i=0;i<req_skills.size();i++)
8        skillToId[req_skills[i]] = i;
9    vector<pair<int,vector<int>>> dp(1<<req_skills.size(),{INT_MAX,{}})
10    dp[0] = {0, {}};
11    for(int i=0;i<people.size();i++){
12        int curr_skill = 0;
13        for(string &skill : people[i]){
14            curr_skill |= (1<<skillToId[skill]);
15        }
16        for(int j=0;j<dp.size();j++){
17            if(dp[j].first+1 < dp[j|curr_skill].first){
18                dp[j|curr_skill] = {dp[j].first + 1, dp[j].second};
19                dp[j|curr_skill].second.push_back(i);
20            }
21        }
22    }
23    return dp.back().second;
24   }
25};

Java Solution

1
2java
3class Solution {
4    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
5        int n = req_skills.length;
6        Map<String, Integer> skillToId = new HashMap<>();
7        for(int i = 0; i < n; i++)
8            skillToId.put(req_skills[i], i);
9        int N = 1 << n;
10        int[] dp = new int[N];
11        Arrays.fill(dp, Integer.MAX_VALUE);
12        dp[0] = 0;
13        List<Integer>[] team = new List[N];
14        team[0] = new ArrayList<>();
15        for(int i = 0; i < people.size(); i++){
16            int person = 0;
17            for(String skill: people.get(i)){
18                if(skillToId.containsKey(skill))
19                    person |= (1 << skillToId.get(skill));
20            }
21            for(int skillset = 0; skillset < N; skillset++){
22                int new_skillset = skillset | person;
23                if(dp[new_skillset] > dp[skillset] + 1){
24                    dp[new_skillset] = dp[skillset] + 1;
25                    team[new_skillset] = new ArrayList<>(team[skillset]);
26                    team[new_skillset].add(i);
27                }
28            }
29        }
30        return team[N - 1].stream().mapToInt(i->i).toArray();
31    }
32}

JavaScript Solution

1
2javascript
3var smallestSufficientTeam = function(req_skills, people) {
4    const skillToId = new Map(), N = req_skills.length;
5    for (let i = 0; i < N; i++)
6        skillToId.set(req_skills[i], i);
7    const dp = new Array(1 << N).fill(N + 1);
8    dp[0] = 0;
9    const res = Array(1 << N).fill(N + 1).map(() => []);
10    for (let i = 0; i < people.length; i++) {
11        let peopleMask = 0;
12        for (const skill of people[i])
13            if (skillToId.has(skill))
14                peopleMask |= (1 << skillToId.get(skill));
15        for (let j = (1 << N) - 1; j >= 0; j--)
16            if (dp[j] + 1 < dp[j | peopleMask]) {
17                dp[j | peopleMask] = dp[j] + 1;
18                res[j | peopleMask] = res[j].concat(i);
19            }
20    }
21    return res[(1 << N) - 1];
22};

C# Solution

1
2csharp
3public class Solution {
4    public int[] SmallestSufficientTeam(string[] req_skills, IList<string[]> people) {
5        Dictionary<string,int> skillToId = new Dictionary<string, int>();
6        for(int i=0; i<req_skills.Length;i++)
7            skillToId[req_skills[i]] = i;
8        int N = 1 << req_skills.Length;
9        int?[] dp = new int?[N];
10        dp[0] = 0;      
11        int[][] team = new int[N][];      
12        for(int i=0; i<people.Count; i++){    
13            int person=0;
14            foreach(string skill in people[i])
15                if(skillToId.ContainsKey(skill))
16                    person |= 1 << skillToId[skill];
17            for(int skillset=0; skillset<N; skillset++){
18                int newSkillSet = skillset | person;
19                if(dp[skillset] != null && (dp[newSkillSet]==null || dp[skillset] + 1 < dp[newSkillSet])){
20                    dp[newSkillSet] = dp[skillset] + 1;
21                    List<int> newTeam = new List<int>();
22                    if(team[skillset] != null )
23                        newTeam.AddRange(team[skillset]);
24                    newTeam.Add(i);  
25                    team[newSkillSet] = newTeam.ToArray();
26                } 
27            }
28        }
29        return team[N-1];
30    }
31}

Each of these solutions has a similar approach but different implementation based on language-specific syntax and features. They all do the task of mapping the required skills to integers and fill up the dynamic programming array and an array (or list) to record the smallest team for each combination of skills. If a person can contribute to a combination of skills (known as a skillset) making the team size smaller, the code updates the dynamic programming array and team array.

In the Python solution, the code uses bitwise operations (shift left '<<' and bitwise OR '|') to generate and manipulate skillsets. The resultant smallest team is returned as a list from the team array.

The C++ solution follows a similar approach as the Python code, returning smallest team from the dp vector.

The Java code also constructs the skill bitmap for every person and checks for each bit combination of the bitmap to find the smallest team covering all skills. The resultant smallest team is converted into an array before returning.

The JavaScript implementation uses a similar strategy, and the resultant smallest team is returned.

The C# solution utilizes the concept of nullable int (int?). The initial value of all elements in dp is null, and through updates made by analyzing every person, it eventually contains the smallest team size corresponding to every possible skillset.

Every solution utilises the concept of dynamic programming and bitmasking to solve the given problem efficiently. These techniques are powerful when dealing with problems involving states or combinations that can be represented as binary or subsets. The bitmask serves as a compact way to represent a subset or state and dynamic programming offers an efficient way to cycle through and process these states or subsets. The key is to define and build the correct mapping between the skills and the bitmask elements.