Problem Description
Given an even-length array of player skills, the task is to divide the players into teams of two such that the sum of skills in each team is equal. The chemistry of a team is defined as the product of the skills of its two players. Return the sum of chemistry for all teams if such a division is possible; otherwise, return -1.
Key Insights
- Sort the array to efficiently pair the smallest and largest skills.
- Calculate the target team sum by using the first and last elements after sorting.
- For every corresponding pair (i and n-1-i), verify if their sum matches the target.
- If any pair does not match the target, it's impossible to form valid teams.
- Accumulate the product of each valid pair (chemistry) if the pairing is valid.
Space and Time Complexity
Time Complexity: O(n log n) due to the sorting step. Space Complexity: O(1) or O(n) depending on the sorting algorithm implementation.
Solution
The strategy begins by sorting the list, which allows us to easily check if we can form pairs that sum up to the same target value by matching the smallest element with the largest element, the second smallest with the second largest, and so on. After determining the target sum using the first and last elements, we iterate over the list checking if each pair conforms to this sum. If any pair deviates, we return -1 as it is impossible to form teams with equal skill sums. Otherwise, we calculate the overall chemistry by summing the product of the skills in each pair. This approach leverages sorting and two pointers to efficiently solve the problem.