LeetCode 1125 - Smallest Sufficient Team

This problem asks us to build the smallest possible team that collectively covers every required skill. We are given two inputs: - reqskills, a list of unique required skills - people, where people[i] contains the skills possessed by person i A team is considered sufficient if…

leetcodehardarraydynamic-programmingbit-manipulationbitmask

LeetCode Problem 1125

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Bit Manipulation, Bitmask

Solution

Problem Understanding

This problem asks us to build the smallest possible team that collectively covers every required skill.

We are given two inputs:

  • req_skills, a list of unique required skills
  • people, where people[i] contains the skills possessed by person i

A team is considered sufficient if every skill in req_skills appears in at least one team member's skill list.

The goal is not to find all valid teams, but specifically one with the minimum number of people.

The output should be a list of indices representing the chosen people.

The constraints are extremely important here:

  • There can be at most 16 required skills
  • There can be up to 60 people

The small number of required skills is the key observation. Since there are only 16 skills maximum, we can represent the set of covered skills using a bitmask. A bitmask of 16 bits can represent every possible subset of skills.

For example:

  • bit 0 represents "java"
  • bit 1 represents "nodejs"
  • bit 2 represents "reactjs"

Then a mask like 101₂ means:

  • "java" is covered
  • "reactjs" is covered
  • "nodejs" is not covered

This transforms the problem into a shortest coverage problem over subsets.

Several edge cases matter:

  • Some people may contribute no useful skills
  • Multiple people may have overlapping skill sets
  • One person may cover many skills at once
  • The optimal solution may not be unique
  • A greedy approach can fail because locally optimal choices do not always produce the globally smallest team

The problem guarantees that at least one sufficient team exists, so we never need to handle impossible cases.

Approaches

Brute Force Approach

The most straightforward solution is to examine every possible subset of people.

For each subset:

  1. Combine all skills possessed by people in that subset
  2. Check whether all required skills are covered
  3. Track the smallest valid subset found

Since there are n people, there are 2^n possible subsets.

With up to 60 people, this becomes completely infeasible:

$$2^{60}$$

This is astronomically large.

Although the brute-force solution is conceptually simple and guaranteed to find the optimal answer, it cannot run within reasonable time limits.

Key Insight

The important observation is that the number of required skills is very small, at most 16.

Instead of tracking subsets of people, we can track subsets of skills.

There are only:

$$2^{16} = 65536$$

possible skill combinations.

This is manageable.

We can use dynamic programming where:

  • the state is a bitmask representing covered skills
  • the value is the smallest team that achieves that mask

For each person:

  • determine which skills they contribute
  • attempt to extend every existing state
  • update the DP table if the new team is smaller

This transforms an exponential-in-people problem into an exponential-in-skills problem, which is tractable because the skill count is tiny.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n × n × s) O(1) Checks every subset of people
Optimal Dynamic Programming with Bitmasking O(n × 2^m) O(2^m) Tracks smallest team for each skill subset

Where:

  • n = number of people
  • m = number of required skills
  • s = average skills per person

Algorithm Walkthrough

Step 1: Assign each skill a bit position

We create a mapping from skill name to bit index.

Example:

"java"   -> 0
"nodejs" -> 1
"reactjs"-> 2

This allows us to efficiently represent skill sets as integers.

Step 2: Convert each person's skills into a bitmask

For every person, we compute a bitmask representing all skills they possess.

Example:

["nodejs", "reactjs"]

becomes:

110₂

This means the person covers skill 1 and skill 2.

Step 3: Initialize the DP table

We use a dictionary:

dp[mask] = smallest team achieving this mask

Initially:

dp[0] = []

Mask 0 means no skills covered, and the empty team achieves that.

Step 4: Process each person

For each person:

  1. Take their skill mask
  2. Iterate through all existing DP states
  3. Combine the person's skills with the existing mask

This gives:

new_mask = old_mask | person_mask

If the new team is smaller than the currently stored team for new_mask, update it.

Step 5: Continue building better states

As more people are processed, the DP table gradually accumulates optimal teams for larger and larger skill subsets.

Since every transition either improves a state or leaves it unchanged, the DP table always stores the smallest known team for each mask.

Step 6: Return the full coverage state

The target mask is:

(1 << number_of_skills) - 1

This represents all skills covered.

We return the team stored for that mask.

Why it works

The DP state invariant is:

dp[mask] always stores the smallest team found so far that covers exactly the skills in mask.

Every possible team can be constructed incrementally by adding people one at a time. During processing, the algorithm considers all such combinations through state transitions.

Whenever a smaller team for a skill set is discovered, it replaces the previous one.

Since all people are processed and every reachable skill subset is explored, the final DP entry for the full skill mask must represent a minimum-sized sufficient team.

Python Solution

from typing import List

class Solution:
    def smallestSufficientTeam(
        self,
        req_skills: List[str],
        people: List[List[str]]
    ) -> List[int]:

        skill_to_bit = {
            skill: i
            for i, skill in enumerate(req_skills)
        }

        people_masks = []

        for skills in people:
            mask = 0

            for skill in skills:
                mask |= 1 << skill_to_bit[skill]

            people_masks.append(mask)

        dp = {0: []}

        for person_index, person_mask in enumerate(people_masks):

            current_dp = list(dp.items())

            for existing_mask, team in current_dp:

                new_mask = existing_mask | person_mask

                if new_mask == existing_mask:
                    continue

                new_team = team + [person_index]

                if (
                    new_mask not in dp
                    or len(new_team) < len(dp[new_mask])
                ):
                    dp[new_mask] = new_team

        full_mask = (1 << len(req_skills)) - 1

        return dp[full_mask]

The implementation begins by converting each required skill into a bit position. This enables constant-time bit operations instead of expensive set comparisons.

Each person's skills are then compressed into a single integer mask. This preprocessing step simplifies later DP transitions.

The DP dictionary stores the smallest team for every achievable skill combination. The key is the skill mask, and the value is the list of selected people indices.

For each person, we iterate over the current DP states. We compute the new covered skill set using bitwise OR. If adding the current person improves the team size for that state, we update the DP table.

The iteration uses list(dp.items()) to avoid modifying the dictionary while iterating over it.

Finally, the algorithm returns the team corresponding to the mask where all required skills are covered.

Go Solution

func smallestSufficientTeam(req_skills []string, people [][]string) []int {

	skillToBit := make(map[string]int)

	for i, skill := range req_skills {
		skillToBit[skill] = i
	}

	peopleMasks := make([]int, len(people))

	for i, skills := range people {

		mask := 0

		for _, skill := range skills {
			mask |= 1 << skillToBit[skill]
		}

		peopleMasks[i] = mask
	}

	dp := make(map[int][]int)
	dp[0] = []int{}

	for personIndex, personMask := range peopleMasks {

		currentStates := make(map[int][]int)

		for k, v := range dp {

			copied := make([]int, len(v))
			copy(copied, v)

			currentStates[k] = copied
		}

		for existingMask, team := range currentStates {

			newMask := existingMask | personMask

			if newMask == existingMask {
				continue
			}

			newTeam := append([]int{}, team...)
			newTeam = append(newTeam, personIndex)

			oldTeam, exists := dp[newMask]

			if !exists || len(newTeam) < len(oldTeam) {
				dp[newMask] = newTeam
			}
		}
	}

	fullMask := (1 << len(req_skills)) - 1

	return dp[fullMask]
}

The Go implementation follows the same logic as the Python version, but there are a few language-specific considerations.

Go slices are mutable references, so we must explicitly copy slices before modifying them. Otherwise, multiple DP states could accidentally share the same underlying array.

The DP table is implemented using a map[int][]int, where the integer key is the skill mask.

Bit operations behave naturally with Go integers because the maximum skill count is only 16, well within standard integer limits.

Worked Examples

Example 1

req_skills = ["java","nodejs","reactjs"]

people = [
    ["java"],
    ["nodejs"],
    ["nodejs","reactjs"]
]

Step 1: Skill Mapping

Skill Bit
java 0
nodejs 1
reactjs 2

Step 2: Person Masks

Person Skills Bitmask
0 ["java"] 001
1 ["nodejs"] 010
2 ["nodejs","reactjs"] 110

Step 3: DP Evolution

Initial:

Mask Team
000 []

After processing person 0:

Mask Team
000 []
001 [0]

After processing person 1:

Mask Team
000 []
001 [0]
010 [1]
011 [0,1]

After processing person 2:

Mask Team
000 []
001 [0]
010 [1]
011 [0,1]
110 [2]
111 [0,2]

Final answer:

[0,2]

Example 2

req_skills =
["algorithms","math","java","reactjs","csharp","aws"]

Skill Mapping

Skill Bit
algorithms 0
math 1
java 2
reactjs 3
csharp 4
aws 5

Person Masks

Person Skills Bitmask
0 algorithms, math, java 000111
1 algorithms, math, reactjs 001011
2 java, csharp, aws 110100
3 reactjs, csharp 011000
4 csharp, math 010010
5 aws, java 100100

The algorithm explores combinations incrementally.

A crucial transition is:

Person 1 mask: 001011
Person 2 mask: 110100
Combined:      111111

This covers all skills with only two people.

Final answer:

[1,2]

Complexity Analysis

Measure Complexity Explanation
Time O(n × 2^m) Each person may update every skill subset
Space O(2^m) DP stores one team per skill mask

Where:

  • n is the number of people
  • m is the number of required skills

The number of DP states is bounded by 2^m. Since m ≤ 16, the maximum number of states is only 65536.

For each person, we potentially iterate through all states once. This yields:

$$O(n \times 2^m)$$

The stored teams contribute additional memory usage, but the number of states still dominates the complexity analysis.

Test Cases

from typing import List

class Solution:
    def smallestSufficientTeam(
        self,
        req_skills: List[str],
        people: List[List[str]]
    ) -> List[int]:

        skill_to_bit = {
            skill: i
            for i, skill in enumerate(req_skills)
        }

        people_masks = []

        for skills in people:
            mask = 0

            for skill in skills:
                mask |= 1 << skill_to_bit[skill]

            people_masks.append(mask)

        dp = {0: []}

        for person_index, person_mask in enumerate(people_masks):

            current_dp = list(dp.items())

            for existing_mask, team in current_dp:

                new_mask = existing_mask | person_mask

                if new_mask == existing_mask:
                    continue

                new_team = team + [person_index]

                if (
                    new_mask not in dp
                    or len(new_team) < len(dp[new_mask])
                ):
                    dp[new_mask] = new_team

        full_mask = (1 << len(req_skills)) - 1

        return dp[full_mask]

sol = Solution()

# Example 1
ans = sol.smallestSufficientTeam(
    ["java", "nodejs", "reactjs"],
    [["java"], ["nodejs"], ["nodejs", "reactjs"]]
)
assert len(ans) == 2  # minimum team size is 2

# Example 2
ans = sol.smallestSufficientTeam(
    ["algorithms","math","java","reactjs","csharp","aws"],
    [
        ["algorithms","math","java"],
        ["algorithms","math","reactjs"],
        ["java","csharp","aws"],
        ["reactjs","csharp"],
        ["csharp","math"],
        ["aws","java"]
    ]
)
assert len(ans) == 2  # optimal answer uses 2 people

# Single required skill
ans = sol.smallestSufficientTeam(
    ["java"],
    [["java"], ["java"]]
)
assert len(ans) == 1  # only one person needed

# One person covers all skills
ans = sol.smallestSufficientTeam(
    ["a", "b", "c"],
    [["a", "b", "c"], ["a"], ["b"]]
)
assert ans == [0]  # single-person solution

# People with no skills
ans = sol.smallestSufficientTeam(
    ["a", "b"],
    [[], ["a"], ["b"]]
)
assert len(ans) == 2  # empty-skill person ignored

# Overlapping skills
ans = sol.smallestSufficientTeam(
    ["a", "b", "c"],
    [["a", "b"], ["b", "c"], ["a", "c"]]
)
assert len(ans) == 2  # requires combining two people

# Redundant people
ans = sol.smallestSufficientTeam(
    ["a", "b"],
    [["a"], ["a"], ["b"]]
)
assert len(ans) == 2  # duplicate skill holders handled

# Maximum skill compression behavior
skills = [f"s{i}" for i in range(16)]
people = [[skill] for skill in skills]

ans = sol.smallestSufficientTeam(skills, people)
assert len(ans) == 16  # every person needed

Test Summary

Test Why
Example 1 Verifies basic DP transitions
Example 2 Verifies optimal multi-skill combination
Single required skill Smallest possible skill count
One person covers all skills Confirms minimal singleton team
People with no skills Ensures useless people are ignored
Overlapping skills Validates non-greedy optimization
Redundant people Ensures duplicates do not break DP
16-skill boundary case Tests maximum bitmask size

Edge Cases

People With No Skills

Some people may have empty skill lists. A naive implementation might still include them in transitions, creating unnecessary states or incorrect updates.

This implementation safely handles them because their mask is 0. When combined with any existing state:

new_mask = existing_mask | 0

the state does not change. The algorithm explicitly skips such non-improving transitions.

Multiple People With Identical Skills

Several people may contribute exactly the same skills. A naive implementation could keep redundant teams and grow unnecessarily large.

The DP update rule only replaces a state when a strictly smaller team is found. Therefore, redundant people naturally get ignored unless they improve the solution.

One Person Covers Every Skill

Sometimes a single person already satisfies all requirements. Greedy or improperly structured solutions may still build larger teams before discovering this.

The bitmask DP handles this immediately. As soon as that person is processed, the full skill mask is reached with team size 1, which is the theoretical minimum and can never be improved.