1125. Smallest Sufficient Team


Problem Description

In this problem, we are working on a project management scenario where we have a list of skills required for a project (req_skills) and a group of people where each person has a set of skills. Our goal is to form the smallest possible team such that each required skill for the project is covered by at least one team member's skill set. The people are represented by indices, and we need to find a subset of these indices such that the corresponding team members collectively possess all the required skills. This set should be as small as possible and the function should return any optimal solution.

Intuition

The intuition behind solving this problem lies in understanding it as a bit manipulation and dynamic programming problem. Each person's skill set can be represented as a bitmask, where each bit corresponds to a particular skill. For example, if we have 5 skills, a person with skills 1 and 3 would be represented as 10100 in binary (or 20 in decimal).

  • Bitmask Representation: This conversion to bitmasks allows us to use bitwise operations to efficiently combine skill sets and check if all required skills are met.

  • Dynamic Programming Approach: We use dynamic programming to track the optimal solution for each possible combination of skills. We initialize an array f where f[i] represents the smallest size of a team that can cover the skill set represented by the bitmask i. Initially, only the empty skill set has a team size of 0.

  • Iterative Solution Building: Then we iterate over all possible combinations of skills. For each combination, we consider adding each person to the team one by one and see if adding them would provide a better solution (i.e., a smaller team size) for the new combination of skills that would result from adding this person's skills to the current combination.

  • Backtracking to Find Team Members: After we populate the dynamic programming table with the minimum team sizes for all combinations, we backtrack from the solution that covers all required skills to find which people make up this optimal team. The arrays g and h help in this backtracking step; g stores the last person added to achieve this combination of skills, and h stores the previous combination of skills before the last person was added.

By using bit manipulation and dynamic programming, we can ensure that we cover all possible teams and arrive at a sufficient team with the smallest possible size.

Learn more about Dynamic Programming and Bitmask patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which data structure is used to implement priority queue?

Solution Approach

The problem is tackled with a combination of bit manipulation and dynamic programming, and here's the detailed walk-through:

  1. Mapping Skills to Bits: First, a dictionary d is created that maps each skill to a unique index. This helps in converting the list of skills for each person into a bitmask where the bit at the index corresponding to a skill is set to 1 if the person has that skill. Initializing people’s skills involves iterating through each person and setting the relevant bits to 1 in their skill representation p[].

  2. Dynamic Programming Initialization: A list f is initialized with inf (infinity) values, where each index of f corresponds to a bitmask of skills. The value at f[i] will store the minimum team size needed to cover the skill set represented by the bitmask i. The entry f[0], which corresponds to a team with no skills, is initially set to 0, as no team members are required to cover no skills.

  3. Building the DP Table: The main loop iterates over all combinations of skills i and for each, checks if it's already been reached (i.e., f[i] is not inf). Then for each person j, it calculates the combination of skills that would result if this person is added to the team (i | p[j]). If this new combination results in a smaller team size than previously recorded, the algorithm updates f[i | p[j]] to this smaller size and records in g the index of the person added, and in h the previous skill combination.

  4. Backtracking to Build the Smallest Team: The solution set bitmask (1 << m) - 1 represents all skills being covered. Starting from this final state, the algorithm uses the arrays g and h to backtrack and construct the smallest sufficient team. The array g contains the indices of the people added, and h tells us the previous state before the person in g was added. By backtracking from the state representing all skills covered, the algorithm adds the indices of the necessary team members into the ans array.

  5. Return the Result: Finally, the array ans containing the indices of the smallest necessary team is returned.

To summarize, we use:

  • Bit Manipulation: To efficiently combine skill sets and evaluate team compositions.
  • Dynamic Programming: To build the minimum team sizes for all possible skill combinations iteratively.
  • Backtracking: To construct the actual team by retracing which people were added at each step.

The algorithm ensures by its design that it will return one of the possible smallest sufficient teams.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Example Walkthrough

Let's consider a simplified example to illustrate the solution approach:

  • The project requires 3 skills, so we need a team to cover these skills: req_skills = ["coding", "math", "data"].
  • There are 3 people available, each with their own set of skills:
    • Person 0 has "coding".
    • Person 1 has "math".
    • Person 2 has "coding" and "data".

Using the solution approach described previously:

  1. Mapping Skills to Bits: We map each skill to a bit position:

    • "coding" -> bit 0
    • "math" -> bit 1
    • "data" -> bit 2

    Now, we represent each person's skills as a bitmask:

    • Person 0: "coding" -> 001 binary -> 1 decimal
    • Person 1: "math" -> 010 binary -> 2 decimal
    • Person 2: "coding", "data" -> 101 binary -> 5 decimal
  2. Dynamic Programming Initialization: We initialize an array f with four elements (since 2^3 skills = 8 combinations, from 000 to 111 in binary):

    • f = [inf, inf, inf, inf, inf, inf, inf, inf]
    • We set f[0] to 0 because no team is needed for no skills: f = [0, inf, inf, inf, inf, inf, inf, inf]
  3. Building the DP Table: We iterate over combinations of skills and update the f table:

    • For bitmask 1 (Person 0): f[1] = 1 because Person 0 can cover the "coding" skill.
    • For bitmask 2 (Person 1): f[2] = 1 because Person 1 can cover the "math" skill.
    • For bitmask 5 (Person 2): f[5] = 1 because Person 2 can cover "coding" and "data".
  4. Backtracking to Build the Smallest Team: We need to cover all skills (111 binary -> 7 decimal). The minimum value of f[7] would be found by considering the combination that includes Person 2 (5) and Person 1 (2):

    • We check f[7] = min(f[7], f[5] + 1) and f[7] = min(f[7], f[2] + 1) because adding either Person 2 or Person 1 to an already covered skill set can potentially meet all requirements.
    • In this case, we see that f[7] is not inf, and the value should be 2. This signifies we need at least 2 team members to cover all the skills.
  5. Return the Result: The smallest team that can cover all skills includes Person 1 and Person 2. They collectively cover all three required skills.

From this example, we start with individual skills, build up our dynamic programming table by iteratively considering each person, and use backtracking to find the actual people that make up the smallest team that covers all necessary skills. The result is a team of two people with indices [1, 2], which successfully covers the required skills for the project.

Not Sure What to Study? Take the 2-min Quiz:

A heap is a ...?

Python Solution

1from sys import maxsize as inf
2from typing import List
3
4class Solution:
5    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
6        # Map each required skill to an index
7        skill_to_index = {skill: index for index, skill in enumerate(req_skills)}
8        num_skills, num_people = len(req_skills), len(people)
9      
10        # Create a bitmask for each person indicating which skills they have
11        people_skills = [0] * num_people
12        for i, skills in enumerate(people):
13            for skill in skills:
14                # Set the bit at the position indicated by the skill index
15                people_skills[i] |= 1 << skill_to_index[skill]
16
17        # Create an array to store the minimal team size needed to cover the skill i
18        min_team_size = [inf] * (1 << num_skills)
19        # Create an array to track the last person added to reach the skill set i
20        last_added_person = [0] * (1 << num_skills)
21        # Create an array to track the previous skill set before adding the last person for i
22        prev_skill_set = [0] * (1 << num_skills)
23
24        # Base case: no skills are covered with team size 0
25        min_team_size[0] = 0
26      
27        # Iterate over all possible sets of skills
28        for skill_set in range(1 << num_skills):
29            # If no team for this skill set, continue
30            if min_team_size[skill_set] == inf:
31                continue
32          
33            # Try adding each person to the current team and see if a smaller team can be formed
34            for j in range(num_people):
35                # Calculate the new skill set after adding this person
36                new_skill_set = skill_set | people_skills[j]
37                # If adding this person leads to a smaller team than previously recorded, update our records
38                if min_team_size[skill_set] + 1 < min_team_size[new_skill_set]:
39                    min_team_size[new_skill_set] = min_team_size[skill_set] + 1
40                    last_added_person[new_skill_set] = j
41                    prev_skill_set[new_skill_set] = skill_set
42
43        # Construct the answer starting from the team that covers all skills
44        current_skill_set = (1 << num_skills) - 1
45        team_indices = []
46      
47        # Work backwards from the final skill set to find the team members by index
48        while current_skill_set:
49            team_indices.append(last_added_person[current_skill_set])
50            current_skill_set = prev_skill_set[current_skill_set]
51
52        return team_indices
53

Java Solution

1import java.util.*;
2
3class Solution {
4    public int[] smallestSufficientTeam(String[] requiredSkills, List<List<String>> people) {
5        // Create a skill index mapping for bitwise representation.
6        Map<String, Integer> skillIndex = new HashMap<>();
7        int skillCount = requiredSkills.length;
8        int peopleCount = people.size();
9        for (int i = 0; i < skillCount; ++i) {
10            skillIndex.put(requiredSkills[i], i);
11        }
12
13        // Transform each person's skill set into a bitmask.
14        int[] peopleSkills = new int[peopleCount];
15        for (int i = 0; i < peopleCount; ++i) {
16            for (String skill : people.get(i)) {
17                peopleSkills[i] |= 1 << skillIndex.get(skill);
18            }
19        }
20
21        // Use dynamic programming to find the smallest sufficient team.
22        final int INF = 1 << 30; // Use a large number to represent infinity.
23        int[] dp = new int[1 << skillCount];
24        int[] lastPersonAdded = new int[1 << skillCount];
25        int[] lastState = new int[1 << skillCount];
26      
27        // Initialize dp array with "infinity" to represent unreachable states.
28        Arrays.fill(dp, INF);
29        dp[0] = 0;
30
31        // Iterate through all possible states.
32        for (int state = 0; state < (1 << skillCount); ++state) {
33            if (dp[state] == INF) {
34                continue; // Skip unreachable states.
35            }
36
37            // Try to add each person to the current state and update the dp array.
38            for (int j = 0; j < peopleCount; ++j) {
39                int newState = state | peopleSkills[j];
40                if (dp[state] + 1 < dp[newState]) {
41                    dp[newState] = dp[state] + 1;
42                    lastPersonAdded[newState] = j;
43                    lastState[newState] = state;
44                }
45            }
46        }
47
48        // Backtrack to find the smallest sufficient team.
49        List<Integer> team = new ArrayList<>();
50        for (int state = (1 << skillCount) - 1; state != 0; state = lastState[state]) {
51            team.add(lastPersonAdded[state]);
52        }
53        // Convert the ArrayList to an array and return the result.
54        return team.stream().mapToInt(Integer::intValue).toArray();
55    }
56}
57

C++ Solution

1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <cstring>
5using namespace std;
6
7class Solution {
8public:
9    vector<int> smallestSufficientTeam(vector<string>& reqSkills, vector<vector<string>>& people) {
10        // Map each skill to a unique index
11        unordered_map<string, int> skillToIndex;
12        int numSkills = reqSkills.size(), numPeople = people.size();
13        for (int i = 0; i < numSkills; ++i) {
14            skillToIndex[reqSkills[i]] = i;
15        }
16
17        // Convert people's skills to bitmask representation
18        vector<int> peopleSkills(numPeople, 0);
19        for (int i = 0; i < numPeople; ++i) {
20            for (string& skill : people[i]) {
21                peopleSkills[i] |= 1 << skillToIndex[skill];
22            }
23        }
24
25        // Initialize the DP arrays
26        // f[state] represents the minimum number of people to form the skills in `state`
27        vector<int> dpMinTeam(1 << numSkills, INT_MAX);
28        // g[state] represents the last person added to achieve `state`
29        vector<int> lastPersonAdded(1 << numSkills);
30        // h[state] represents the previous state before adding lastPersonAdded
31        vector<int> prevState(1 << numSkills);
32        dpMinTeam[0] = 0;
33
34        // Iterate through all possible states of skill combinations
35        for (int state = 0; state < (1 << numSkills); ++state) {
36            if (dpMinTeam[state] == INT_MAX) {
37                continue; // Skip if this state is not achievable
38            }
39            // Consider adding each person one by one to the current state
40            for (int person = 0; person < numPeople; ++person) {
41                int newState = state | peopleSkills[person];
42                if (dpMinTeam[state] + 1 < dpMinTeam[newState]) {
43                    // If adding this person improves the team, update the DP arrays
44                    dpMinTeam[newState] = dpMinTeam[state] + 1;
45                    lastPersonAdded[newState] = person;
46                    prevState[newState] = state;
47                }
48            }
49        }
50
51        // Reconstruct the smallest sufficient team
52        vector<int> smallestTeam;
53        int currentState = (1 << numSkills) - 1; // Start with all skills covered
54        while (currentState) { // until we reach the empty state
55            smallestTeam.push_back(lastPersonAdded[currentState]);
56            currentState = prevState[currentState]; // Go to the previous state
57        }
58
59        return smallestTeam;
60    }
61};
62

Typescript Solution

1function smallestSufficientTeam(reqSkills: string[], people: string[][]): number[] {
2    // Create a mapping from the required skills to their corresponding indices
3    const skillToIndex: Map<string, number> = new Map();
4    const skillCount = reqSkills.length;
5    const peopleCount = people.length;
6    for (let i = 0; i < skillCount; ++i) {
7        skillToIndex.set(reqSkills[i], i);
8    }
9
10    // Encode the skills of each person as a bitmask integer
11    const peopleSkills: number[] = new Array(peopleCount).fill(0);
12    for (let i = 0; i < peopleCount; ++i) {
13        for (const skill of people[i]) {
14            peopleSkills[i] |= 1 << skillToIndex.get(skill)!; // '!' assures TypeScript that the value is not null/undefined
15        }
16    }
17
18    const MAX_INT = 1 << 30; // Use a large number as the equivalent of infinity
19    // f represents the minimum team size needed to cover the skills represented by the bitmask
20    const teamSize: number[] = new Array(1 << skillCount).fill(MAX_INT);
21    // g represents the last person added to the team for the given skill set
22    const lastPersonAdded: number[] = new Array(1 << skillCount).fill(0);
23    // h represents the previous state of the team before the last person was added
24    const prevState: number[] = new Array(1 << skillCount).fill(0);
25  
26    // Initialize base case - no skills covered with team size 0
27    teamSize[0] = 0;
28  
29    // Compute the smallest team for all combinations of skills
30    for (let i = 0; i < (1 << skillCount); ++i) {
31        if (teamSize[i] === MAX_INT) continue;
32
33        for (let j = 0; j < peopleCount; ++j) {
34            const combinedSkills = i | peopleSkills[j]; // Combine current skills with this person's skills
35            if (teamSize[i] + 1 < teamSize[combinedSkills]) {
36                // Found a smaller team, update arrays
37                teamSize[combinedSkills] = teamSize[i] + 1;
38                lastPersonAdded[combinedSkills] = j;
39                prevState[combinedSkills] = i;
40            }
41        }
42    }
43
44    // Backtrack to build the team starting from the complete skill set
45    const teamMembers: number[] = [];
46    for (let i = (1 << skillCount) - 1; i > 0; i = prevState[i]) {
47        teamMembers.push(lastPersonAdded[i]);
48    }
49
50    // Return the indices of the smallest sufficient team
51    return teamMembers.reverse(); // The team was built in reverse order, so reverse it before returning
52}
53
Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Time and Space Complexity

Time Complexity

The given code implements a dynamic programming solution to find the smallest sufficient team for the required skills. Here's a step-by-step analysis of the time complexity:

  • The dictionary creation d = {s: i for i, s in enumerate(req_skills)} takes O(m) time where m is the number of required skills.
  • Preparing the array p requires iterating over each person and each skill of that person. If we denote the average number of skills per person as s_avg, this step takes O(n * s_avg) where n is the number of people.
  • Initializing the arrays f, g, and h each takes O(1 << m) time.
  • The nested loops iterate over each combination of skills (i) and each person (j). For each person, we might update the state, so the complexity of these nested loops is O(n * 2^m).
  • Finally, there's a while loop to reconstruct the solution. In the worst case, it could take O(n) time since we might select each person once.

Given the above, the overall time complexity of the solution is dominated by O(n * 2^m).

Space Complexity

Now let's analyze the space complexity:

  • The dictionary d has as many entries as there are unique skills, resulting in O(m) space.
  • The array p has a size of n, giving O(n).
  • The arrays f, g, and h each consume space proportional to 2^m, therefore each taking O(2^m).

Summing up the space used by these elements, the overall space complexity is O(2^m + m + n).

In conclusion, the final computational complexity for the code is:

  • Time Complexity: O(n * 2^m)
  • Space Complexity: O(2^m + m + n)

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫