Taro Logo

Smallest Sufficient Team

Hard
Google logo
Google
Topics:
Dynamic ProgrammingBit Manipulation

You are given a list of required skills, req_skills, and a list of people. Each person people[i] has a list of skills they possess.

A sufficient team is a set of people where for every required skill in req_skills, at least one person in the team has that skill. You can represent a team by the indices of the people in the team.

For example, if team = [0, 1, 3], it represents the people with skills people[0], people[1], and people[3].

Your task is to return any sufficient team of the smallest possible size, represented by the indices of the people in the team. The order of the indices in the result doesn't matter. It is guaranteed that a solution exists.

Example 1:

req_skills = ["java", "nodejs", "reactjs"]
people = [["java"], ["nodejs"], ["nodejs", "reactjs"]]
Output: [0, 2]

Example 2:

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 <= people.length <= 60
  • Skills are lowercase English letters.
  • All skills in req_skills are unique.
  • All skills of a person are unique.
  • Every skill a person has is a skill in req_skills.

How would you approach this problem efficiently?

Solution


Naive Approach (Brute Force)

The most straightforward approach is to generate all possible subsets of people and check if each subset forms a sufficient team. Then, find the smallest such team.

  1. Generate all subsets: Create all possible combinations of people indices.
  2. Check sufficiency: For each subset, check if it covers all required skills.
  3. Find the minimum: Keep track of the smallest sufficient team found so far.

Code (Python)

from itertools import combinations

def smallestSufficientTeam_brute_force(req_skills, people):
    skill_map = {skill: i for i, skill in enumerate(req_skills)}
    n_skills = len(req_skills)
    
    people_masks = []
    for person_skills in people:
        mask = 0
        for skill in person_skills:
            mask |= (1 << skill_map[skill])
        people_masks.append(mask)
    
    for team_size in range(1, len(people) + 1):
        for team in combinations(range(len(people)), team_size):
            covered_mask = 0
            for person_index in team:
                covered_mask |= people_masks[person_index]
            if covered_mask == (1 << n_skills) - 1:
                return list(team)
    return []

Time Complexity

  • Generating all subsets takes O(2P) time, where P is the number of people.
  • Checking each subset's sufficiency takes O(N), where N is the number of required skills. In the worst case, it can go through all people.
  • Overall: O(2P * N), which is exponential.

Space Complexity

  • O(P) to store the subset.
  • O(N) for skill map.
  • O(P) to store the people masks.
  • Overall: O(P + N)

Optimal Approach (Dynamic Programming with Bit Masking)

We can significantly improve the efficiency by using dynamic programming with bit masking. The idea is to represent the covered skills as a bitmask. Each bit in the mask corresponds to a skill. If the i-th bit is set, it means the i-th skill is covered.

  1. Skill Mapping: Create a mapping from skills to bit positions.
  2. People Masks: Create a bitmask for each person representing the skills they possess.
  3. DP State: dp[mask] stores the smallest team required to cover the skills represented by the bitmask mask.
  4. DP Transition: Iterate through each person. For each person, update the dp array. If adding the person to the current team results in a smaller team size for a given covered skill set, update the dp array.

Code (Python)

def smallestSufficientTeam(req_skills, people):
    n = len(req_skills)
    skill_id = {s: i for i, s in enumerate(req_skills)}

    dp = {0: []}
    for i, p in enumerate(people):
        skills_mask = 0
        for skill in p:
            skills_mask |= 1 << skill_id[skill]

        for mask, team in list(dp.items()):
            new_mask = mask | skills_mask
            if new_mask not in dp or len(team) + 1 < len(dp[new_mask]):
                dp[new_mask] = team + [i]

    return dp[(1 << n) - 1]

Time Complexity

  • O(P * 2N), where P is the number of people and N is the number of required skills. We iterate through each person and each possible mask.

Space Complexity

  • O(2N) to store the dp array, where N is the number of required skills.

Edge Cases

  • Empty req_skills: If req_skills is empty, any empty team will be a sufficient team, so return an empty list.
  • Empty people: If people is empty and req_skills is not empty, then there is no sufficient team which violates the constraints. The problem states it is guaranteed a sufficient team exists, so this edge case does not need to be handled.
  • Duplicate skills within a person's skills: The problem statement specifies that all skills of a person are unique, therefore no edge case to handle.