LeetCode 1125: Smallest Sufficient Team Solution

Master LeetCode problem 1125 (Smallest Sufficient Team), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1125. Smallest Sufficient Team

Hard

Array Dynamic Programming Bit Manipulation Bitmask

Problem Explanation

Explanation

To solve this problem, we can use a dynamic programming approach with bit manipulation. We will create a bitmask to represent the set of skills covered by each possible team. We will iterate through all possible combinations of team members and update the bitmask accordingly. By doing so, we can find the smallest sufficient team that covers all required skills.

Create a mapping of skills to their indices to easily convert between skill names and their corresponding bit positions in the bitmask.
Initialize a dp array where dp[mask] stores the minimum number of team members required to cover all skills represented by the bitmask.
Iterate through each person and update the dp array based on the skills they possess.
Update the dp array by considering the current person in or out of the team, based on whether adding them helps in covering more skills.
Finally, reconstruct the smallest sufficient team by backtracking through the dp array.

Time Complexity: O(2^n * m), where n is the number of people and m is the number of required skills.
Space Complexity: O(2^n)

Solution Code

class Solution {
    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        int n = req_skills.length;
        Map<String, Integer> skillMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            skillMap.put(req_skills[i], i);
        }
        
        int[] dp = new int[1 << n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        List<Integer>[] teamMembers = new List[1 << n];
        Arrays.fill(teamMembers, new ArrayList<>());
        
        for (int i = 0; i < people.size(); i++) {
            int mask = 0;
            for (String skill : people.get(i)) {
                mask |= 1 << skillMap.get(skill);
            }
            
            for (int prev = 0; prev < dp.length; prev++) {
                if (dp[prev] + 1 < dp[prev | mask]) {
                    dp[prev | mask] = dp[prev] + 1;
                    teamMembers[prev | mask] = new ArrayList<>(teamMembers[prev]);
                    teamMembers[prev | mask].add(i);
                }
            }
        }
        
        List<Integer> result = teamMembers[(1 << n) - 1];
        int[] resArray = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            resArray[i] = result.get(i);
        }
        
        return resArray;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1125 (Smallest Sufficient Team)?

This page provides optimized solutions for LeetCode problem 1125 (Smallest Sufficient Team) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1125 (Smallest Sufficient Team)?

The time complexity for LeetCode 1125 (Smallest Sufficient Team) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1125 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1125 in Java, C++, or Python.

Back to LeetCode Solutions