Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5

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:

1
2
3
4

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.

Solution

Video explanation

Here is the video explaining all the methods below in detail. Please check it out:

Method 1 - Using sorting and two sum like approach

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class Solution {
    public long dividePlayers(int[] skill) {
        Arrays.sort(skill); // Sort the array to facilitate pairing.
        int n = skill.length;
        int l = 0, r = n - 1; // Initialize two pointers, one at the beginning and one at the end.
        long tgtSkill = skill[l] + skill[r]; // Calculate the target skill sum for each pair.
        long totalChem = 0; // Initialize the total chemistry.

        // Loop through the array to form pairs.
        while(l < r) {
            long pairSum = skill[l] + skill[r]; // Calculate the sum of the current pair.
            if (pairSum != tgtSkill) {
                return -1;  // Return -1 if the pair's sum doesn't match the target sum.
            }
            totalChem += skill[l] * skill[r]; // Add the product of the current pair to total chemistry.
            l++; // Move the left pointer to the right.
            r--; // Move the right pointer to the left.
        }

        return totalChem; // Return the total chemistry.
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def dividePlayers(self, skill: List[int]) -> int:
        skill.sort()  # Sort the array
        n = len(skill)
        l, r = 0, n - 1
        tgt_skill = skill[l] + skill[r]
        total_chem = 0

        while l < r:
            pair_sum = skill[l] + skill[r]
            if pair_sum != tgt_skill:
                return -1  # Not possible to form teams with equal total skill
            total_chem += skill[l] * skill[r]
            l += 1
            r -= 1

        return total_chem

Complexity

  • ⏰ Time complexity: O(n log n)
    • Sorting the array takes O(n log n).
    • Iterating through the array with two pointers takes O(n).
  • 🧺 Space complexity: O(1),  if we don’t consider the input array as part of the space calculation, as sorting is done in place and only a few extra variables are used.

Method 2 - Using Map

If all the skills have to be equal, how about divide the total skills by n/2 number of teams, to get average team skill.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

public class Solution {
    public long dividePlayers(int[] skill) {
        Map<Integer, Integer> map = new HashMap<>();
        int sum = 0;
        int n = skill.length;
        
        // Populate the map with the skill frequencies and calculate the total sum of skills
        for (int num : skill) {
            sum += num;
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        
        // Check if the sum can be evenly divided by n/2
        if (sum % (n / 2) != 0) {
            return -1;
        }
        
        int tgtSkill = sum / (n / 2); // Target skill sum for each pair
        long totalChem = 0;
        
        // Iterate through the skills array
        for (int num : skill) {
            // Find the remaining skill to pair with the current skill
            int remSkill = tgtSkill - num;
            
            // Check if the remaining skill is available in the map
            if (!map.containsKey(remSkill) || map.get(remSkill) <= 0) {
                return -1;
            }
            
            // Decrease the count of the remaining skill as it is used now
            map.put(remSkill, map.get(remSkill) - 1);
            
            // Calculate the product of the current skill and the remaining skill
            totalChem += (long) num * remSkill;
        }
        
        return totalChem / 2; // Return the total chemistry
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution:
    def dividePlayers(self, skill: List[int]) -> int:
        skill_map = defaultdict(int)
        total_sum = 0
        n = len(skill)
        
        # Populate the map with the skill frequencies and calculate the total sum of skills
        for num in skill:
            total_sum += num
            skill_map[num] += 1
        
        # Check if the sum can be evenly divided by n/2
        if total_sum % (n // 2) != 0:
            return -1
        
        target_skill_sum = total_sum // (n // 2)  # Target skill sum for each pair
        total_chemistry = 0
        
        # Iterate through the skills array
        for num in skill:
            # Find the target skill to pair with the current skill
            target = target_skill_sum - num
            
            # Check if the target skill is available in the map
            if skill_map[target] <= 0:
                return -1
            
            # Decrease the count of the target skill as it is used now
            skill_map[target] -= 1
            
            # Calculate the product of the current skill and the target skill
            total_chemistry += num * target
        
        return total_chemistry // 2  # Return the total chemistry

Complexity

  • ⏰ Time complexity: O(n)
    • Building the frequency map and calculating the total sum takes O(n).
    • Iterating through the array to form pairs also takes O(n).
  • 🧺 Space complexity: O(n), due to the use of the map to store the skill frequencies.