Smallest Sufficient Team - Practice Coding Problems

Smallest Sufficient Team - Problem

In a project, you have a list of required skills req_skills, and a list of people. The i-th 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.

Input & Output

Example 1 — Basic Team Formation

$ Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]

› Output: [0,2]

💡 Note: Person 0 has java, Person 2 has nodejs and reactjs. Together they cover all required skills [java, nodejs, reactjs]

Example 2 — Minimal Team

$ 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]

💡 Note: Person 1 covers [algorithms,math,reactjs] and Person 2 covers [java,csharp,aws]. Together they have all 6 skills.

Example 3 — Single Person Team

$ Input: req_skills = ["cooking"], people = [["cooking","baking"],["art"]]

› Output: [0]

💡 Note: Only Person 0 has the cooking skill, so they form the minimal sufficient team

Constraints

1 ≤ req_skills.length ≤ 16
1 ≤ people.length ≤ 60
1 ≤ people[i].length, req_skills[i].length, people[i][j].length ≤ 16
Elements of req_skills are distinct
req_skills[i] and people[i][j] consist of lowercase English letters only
Every skill in people[i] is also in req_skills
It is guaranteed an answer exists

Visualization

Tap to expand

Understanding the Visualization

Input

Required skills and people with their skill sets

Process

Find minimal combination covering all skills

Output

Indices of people forming smallest sufficient team

Key Takeaway

🎯 Key Insight: Use bitmasks to represent skill combinations and DP to efficiently build minimal teams

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Facebook 12

The key insight is to use bitmasks to efficiently represent skill sets and dynamic programming to build minimal teams. Convert each skill to a bit position and each person's skills to a bitmask. Use DP where dp[mask] represents the smallest team covering skills in the mask. Best approach is Bitmask DP with Time: O(n × 2ᵐ), Space: O(2ᵐ) where n is people count and m is skills count.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2ⁿ × m × k)	O(n)	Generate all possible team combinations and find the smallest sufficient one
Bitmask Dynamic Programming	O(n × 2ᵐ)	O(2ᵐ)	Use bitmasks to represent skill sets and DP to find minimal team coverage

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible team combinations starting from size 1
For each combination, check if it covers all required skills
Return the first valid combination found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Teams

Create all possible team combinations starting from size 1

Check Coverage

For each team, verify if all required skills are covered

Return First Valid

Return the first team that covers all skills

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int* solution(char** req_skills, int req_size, char*** people, int* people_sizes, int people_count, int* returnSize) {
    *returnSize = 0;
    
    // Try all team sizes from 1 to people_count
    for (int size = 1; size <= people_count; size++) {
        // Generate all combinations of this size using bit manipulation
        for (int mask = 0; mask < (1 << people_count); mask++) {
            if (__builtin_popcount(mask) != size) continue;
            
            // Check if this team covers all skills
            bool covered[req_size];
            memset(covered, false, sizeof(covered));
            
            for (int i = 0; i < people_count; i++) {
                if (mask & (1 << i)) {
                    // Person i is in the team
                    for (int j = 0; j < people_sizes[i]; j++) {
                        // Check if this skill is required
                        for (int k = 0; k < req_size; k++) {
                            if (strcmp(people[i][j], req_skills[k]) == 0) {
                                covered[k] = true;
                            }
                        }
                    }
                }
            }
            
            // Check if all skills are covered
            bool valid = true;
            for (int i = 0; i < req_size; i++) {
                if (!covered[i]) {
                    valid = false;
                    break;
                }
            }
            
            if (valid) {
                int* result = (int*)malloc(size * sizeof(int));
                int idx = 0;
                for (int i = 0; i < people_count; i++) {
                    if (mask & (1 << i)) {
                        result[idx++] = i;
                    }
                }
                *returnSize = size;
                return result;
            }
        }
    }
    
    return NULL;
}

int main() {
    // This is a simplified version for demonstration
    // Full parsing would be more complex
    printf("[0,1]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × m × k)

2ⁿ subsets of people, m skills to check, k average skills per person

✓ Linear Growth

Space Complexity

O(n)

Space for storing current team combination

⚡ Linearithmic Space

40.8K Views

Medium Frequency

~35 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler