Smallest Sufficient Team

Problem

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.

• For example, 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.

Examples

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 <= 16
• 1 <= req_skills[i].length <= 16
• req_skills[i] consists of lowercase English letters.
• All the strings of req_skills are unique.
• 1 <= people.length <= 60
• 0 <= people[i].length <= 16
• 1 <= people[i][j].length <= 16
• people[i][j] consists of lowercase English letters.
• All the strings of people[i] are unique.
• Every skill in people[i] is a skill in req_skills.
• It is guaranteed a sufficient team exists.

Solution

Method 1 – Bitmask Dynamic Programming 1

Intuition

The key idea is to represent each skill as a bit in an integer, and use dynamic programming to keep track of the smallest team for each possible combination of skills. By iterating through people and updating the DP table, we can efficiently find the smallest sufficient team.

Approach

1. Map each required skill to a unique bit position.
2. For each person, compute a bitmask representing their skills.
3. Use a DP dictionary where the key is the skill bitmask and the value is the list of people indices forming the smallest team for that skill set.
4. Iterate through each person and update the DP table for all skill sets they can help complete.
5. The answer is the team corresponding to the bitmask where all skills are set.

Code

C++

class Solution {
public:
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        int n = req_skills.size();
        unordered_map<string, int> skill_idx;
        for (int i = 0; i < n; ++i) skill_idx[req_skills[i]] = i;
        vector<int> p_mask;
        for (auto& p : people) {
            int mask = 0;
            for (auto& s : p) mask |= 1 << skill_idx[s];
            p_mask.push_back(mask);
        }
        unordered_map<int, vector<int>> dp;
        dp[0] = {};
        for (int i = 0; i < p_mask.size(); ++i) {
            auto dp_copy = dp;
            for (auto& [mask, team] : dp_copy) {
                int new_mask = mask | p_mask[i];
                if (!dp.count(new_mask) || dp[new_mask].size() > team.size() + 1) {
                    dp[new_mask] = team;
                    dp[new_mask].push_back(i);
                }
            }
        }
        return dp[(1 << n) - 1];
    }
};

Go

func smallestSufficientTeam(reqSkills []string, people [][]string) []int {
    n := len(reqSkills)
    skillIdx := map[string]int{}
    for i, s := range reqSkills {
        skillIdx[s] = i
    }
    pMask := make([]int, len(people))
    for i, p := range people {
        for _, s := range p {
            pMask[i] |= 1 << skillIdx[s]
        }
    }
    dp := map[int][]int{0: {}}
    for i, mask := range pMask {
        dpCopy := map[int][]int{}
        for k, v := range dp {
            dpCopy[k] = append([]int{}, v...)
        }
        for m, team := range dpCopy {
            newMask := m | mask
            if _, ok := dp[newMask]; !ok || len(dp[newMask]) > len(team)+1 {
                dp[newMask] = append(append([]int{}, team...), i)
            }
        }
    }
    return dp[(1<<n)-1]
}

Java

class Solution {
    public int[] smallestSufficientTeam(List<String> req_skills, List<List<String>> people) {
        int n = req_skills.size();
        Map<String, Integer> skillIdx = new HashMap<>();
        for (int i = 0; i < n; ++i) skillIdx.put(req_skills.get(i), i);
        int[] pMask = new int[people.size()];
        for (int i = 0; i < people.size(); ++i) {
            for (String s : people.get(i)) pMask[i] |= 1 << skillIdx.get(s);
        }
        Map<Integer, List<Integer>> dp = new HashMap<>();
        dp.put(0, new ArrayList<>());
        for (int i = 0; i < pMask.length; ++i) {
            Map<Integer, List<Integer>> dpCopy = new HashMap<>(dp);
            for (Map.Entry<Integer, List<Integer>> entry : dpCopy.entrySet()) {
                int newMask = entry.getKey() | pMask[i];
                List<Integer> team = new ArrayList<>(entry.getValue());
                team.add(i);
                if (!dp.containsKey(newMask) || dp.get(newMask).size() > team.size()) {
                    dp.put(newMask, team);
                }
            }
        }
        List<Integer> ans = dp.get((1 << n) - 1);
        return ans.stream().mapToInt(i -> i).toArray();
    }
}

Kotlin

class Solution {
    fun smallestSufficientTeam(reqSkills: List<String>, people: List<List<String>>): IntArray {
        val n = reqSkills.size
        val skillIdx = reqSkills.withIndex().associate { it.value to it.index }
        val pMask = people.map { p -> p.fold(0) { acc, s -> acc or (1 shl skillIdx[s]!!) } }
        val dp = mutableMapOf(0 to listOf<Int>())
        for (i in pMask.indices) {
            val dpCopy = dp.toMap()
            for ((mask, team) in dpCopy) {
                val newMask = mask or pMask[i]
                if (newMask !in dp || dp[newMask]!!.size > team.size + 1) {
                    dp[newMask] = team + i
                }
            }
        }
        return dp[(1 shl n) - 1]!!.toIntArray()
    }
}

Python

def smallestSufficientTeam(req_skills: list[str], people: list[list[str]]) -> list[int]:
    n = len(req_skills)
    skill_idx = {s: i for i, s in enumerate(req_skills)}
    p_mask = [(sum(1 << skill_idx[s] for s in p)) for p in people]
    dp: dict[int, list[int]] = {0: []}
    for i, mask in enumerate(p_mask):
        dp_copy = dp.copy()
        for m, team in dp_copy.items():
            new_mask = m | mask
            if new_mask not in dp or len(dp[new_mask]) > len(team) + 1:
                dp[new_mask] = team + [i]
    return dp[(1 << n) - 1]

Rust

impl Solution {
    pub fn smallest_sufficient_team(req_skills: Vec<String>, people: Vec<Vec<String>>) -> Vec<i32> {
        use std::collections::HashMap;
        let n = req_skills.len();
        let mut skill_idx = HashMap::new();
        for (i, s) in req_skills.iter().enumerate() {
            skill_idx.insert(s, i);
        }
        let p_mask: Vec<usize> = people.iter().map(|p| p.iter().fold(0, |acc, s| acc | (1 << skill_idx[s]))) .collect();
        let mut dp: HashMap<usize, Vec<i32>> = HashMap::new();
        dp.insert(0, vec![]);
        for (i, &mask) in p_mask.iter().enumerate() {
            let dp_copy = dp.clone();
            for (&m, team) in dp_copy.iter() {
                let new_mask = m | mask;
                if !dp.contains_key(&new_mask) || dp[&new_mask].len() > team.len() + 1 {
                    let mut new_team = team.clone();
                    new_team.push(i as i32);
                    dp.insert(new_mask, new_team);
                }
            }
        }
        dp[&(1 << n) - 1].clone()
    }
}

TypeScript

class Solution {
    smallestSufficientTeam(reqSkills: string[], people: string[][]): number[] {
        const n = reqSkills.length;
        const skillIdx: Record<string, number> = {};
        reqSkills.forEach((s, i) => skillIdx[s] = i);
        const pMask = people.map(p => p.reduce((acc, s) => acc | (1 << skillIdx[s]), 0));
        const dp: Record<number, number[]> = {0: []};
        for (let i = 0; i < pMask.length; ++i) {
            const dpCopy = {...dp};
            for (const mask in dpCopy) {
                const newMask = Number(mask) | pMask[i];
                if (!(newMask in dp) || dp[newMask].length > dpCopy[mask].length + 1) {
                    dp[newMask] = [...dpCopy[mask], i];
                }
            }
        }
        return dp[(1 << n) - 1];
    }
}

Complexity

• ⏰ Time complexity: O(n * 2^n * m), where n is the number of skills and m is the number of people. For each person, we may update up to 2^n skill sets.
• 🧺 Space complexity: O(2^n * n), for storing the DP table and teams for each skill set.