Leetcode Daily Question 04/10/2024 - 2491. Divide Players Into Teams of Equal Skill

Problem Description:

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.

from typing import List
from collections import Counter
class Solution:
  def dividePlayers(self, skill: List[int]) -> int:
    n = len(skill)
    total = sum(skill)
    if total % (n // 2) != 0:
      return -1
    
    chemistry = 0
    freq_count = Counter(skill)
    target = total // (n // 2)
    
    for key, val in freq_count.items():
      complement = target - key
      if complement not in freq_count or freq_count[complement] != val:
        return -1
      chemistry += key * val * complement
    
    return chemistry // 2

Explanation:

To effectively split skill into pairs of the same sum, we want to pair the current smallest element with the current largest element.

Before we proceed, we first check if this splitting is possible. Since the sum of each pair must be equal, this sum must be equal to the total sum of skill divided by half the length of skills.

def dividePlayers(skill):
  n = len(skill) 
  total = sum(skill)
  if total % (n // 2) != 0:
    return -1

Then we use a dictionary, freq_count, to count the frequency of each element in skill to avoid sorting. We can do this using the Python in-built Counter() method in collections.

For each element "key" in the dictionary, we want to find the corresponding complement, target - key. This key must satisfy two conditions:
1. The complement has to be in freq_count.
2. The frequency of complement has to match frequency of key, otherwise, we will have a mismatched pair at the end.

If these conditions are satisfied, then we can calculate the chemistry of the pair.

chemistry = 0
freq_count = Counter(skill)
target = total // (n // 2)

for key, val in freq_count.items():
  complement = target - key
  if complement not in freq_count or freq_count[complement] != val:
    return -1
  chemistry += key * val * complement
  
return chemistry // 2  # Since we double counted every element.

The time complexity is O(n) as we need to iterate over skill to create the dictionary.

The space complexity is O(n) as well, since we store a maximum of n elements in the dictionary.

The full solution can be found near the top of the page.