Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1220. Smallest Sufficient Team

My accepted Python solution to LeetCode problem 1220, Smallest Sufficient Team, running in 95ms.

  • Difficulty: Hard
  • Python
  • Runtime 95ms
  • Memory 24.2MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 95ms, memory 24.2MB, accepted 2026-01-02.

python
class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n = len(req_skills)
        skill_to_idx = {skill: i for i, skill in enumerate(req_skills)}
        
        # Convert each person's skills to bitmask
        people_masks = []
        for person in people:
            mask = 0
            for skill in person:
                if skill in skill_to_idx:
                    mask |= (1 << skill_to_idx[skill])
            people_masks.append(mask)
        
        target = (1 << n) - 1
        
        # dp[mask] = minimum team to achieve this skill mask
        dp = {0: []}
        
        for i, person_mask in enumerate(people_masks):
            new_dp = {}
            for mask, team in dp.items():
                new_mask = mask | person_mask
                if new_mask not in dp or len(team) + 1 < len(dp[new_mask]):
                    if new_mask not in new_dp or len(team) + 1 < len(new_dp[new_mask]):
                        new_dp[new_mask] = team + [i]
            for mask, team in new_dp.items():
                if mask not in dp or len(team) < len(dp[mask]):
                    dp[mask] = team
        
        return dp[target]

Source