2491. Divide Players Into Teams of Equal Skill

You are given a positive integer array skill of even length n where skill[i] denotes the skill of the ith player. Divide the players into n / 2 teams of size 2 such that the total skill of each team is equal.

The chemistry of a team is equal to the product of the skills of the players on that team.

Return the sum of the chemistry of all the teams, or return -1 if there is no way to divide the players into teams such that the total skill of each team is equal.

Example 1:

Input: skill = [3,2,5,1,3,4]
Output: 22
Explanation:
Divide the players into the following teams: (1, 5), (2, 4), (3, 3), where each team has a total skill of 6.
The sum of the chemistry of all the teams is: 1 * 5 + 2 * 4 + 3 * 3 = 5 + 8 + 9 = 22.

Example 2:

Input: skill = [3,4]
Output: 12
Explanation:
The two players form a team with a total skill of 7.
The chemistry of the team is 3 * 4 = 12.

Example 3:

Input: skill = [1,1,2,3]
Output: -1
Explanation:
There is no way to divide the players into teams such that the total skill of each team is equal.

Constraints:

• 2 <= skill.length <= 105
• skill.length is even.
• 1 <= skill[i] <= 1000

Approach 01:

class Solution {
public:
    long long dividePlayers(std::vector<int>& skillLevels) {
        const int numPlayers = skillLevels.size();
        const int targetTeamSkill = std::accumulate(skillLevels.begin(), skillLevels.end(), 0) / (numPlayers / 2);
        long long totalSkillProduct = 0;
        std::unordered_map<int, int> skillCount;

        for (const int skill : skillLevels)
            ++skillCount[skill];

        for (const auto& [skill, frequency] : skillCount) {
            const int requiredSkill = targetTeamSkill - skill;
            if (const auto it = skillCount.find(requiredSkill);
                it == skillCount.cend() || it->second != frequency)
                return -1;
            totalSkillProduct += static_cast<long long>(skill) * requiredSkill * frequency;
        }

        return totalSkillProduct / 2;
    }
};

class Solution:
    def dividePlayers(self, skillLevels: List[int]) -> int:
        numPlayers = len(skillLevels)
        targetTeamSkill = sum(skillLevels) // (numPlayers // 2)
        totalSkillProduct = 0
        skillCount = {}

        for skill in skillLevels:
            skillCount[skill] = skillCount.get(skill, 0) + 1

        for skill, frequency in skillCount.items():
            requiredSkill = targetTeamSkill - skill
            if skillCount.get(requiredSkill, 0) != frequency:
                return -1
            totalSkillProduct += skill * requiredSkill * frequency

        return totalSkillProduct // 2

Time Complexity

• Calculating target team skill:

  The function uses std::accumulate to calculate the total sum of skillLevels, which takes \(O(n)\), where \(n\) is the number of players. Dividing this total sum by numPlayers / 2 is a constant-time operation, \(O(1)\).

• Counting skill frequencies:

  The function iterates over the skillLevels vector and counts the frequency of each skill using an unordered map, which takes \(O(n)\) time since each skill is processed once.

• Finding pairs of skills:

  For each unique skill in the skillCount map, the function calculates the required complement skill and checks its frequency. This process iterates over the map entries, which takes \(O(n)\) in the worst case, where all skill levels are unique.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where \(n\) is the number of players, since all major operations (summing skills, counting frequencies, checking pairs) scale linearly with the size of the input.

Space Complexity

• Auxiliary Space:

  The function uses an unordered map (skillCount) to store the frequency of each skill, which requires \(O(n)\) space where \(n\) is the number of players. Additionally, a few integer and long long variables are used, which require constant space, \(O(1)\).

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), where \(n\) is the number of players, due to the space required by the unordered map to store skill frequencies.