2491. Divide Players Into Teams of Equal Skill - Detailed Explanation

Problem Statement

Problem Description:
You are given an array skill where each element represents the skill level of a player. The number of players is even. Your task is to pair up all players into teams such that every team has the same total skill (i.e. the sum of the skills of the two players in each team is identical). If it is possible to form such teams, return the sum of the products of the players’ skills for each team; otherwise, return -1.

Example Inputs & Outputs:

1. Example 1:

   • Input: [3, 2, 5, 1, 3, 4]
   • Process:
     • After sorting, the array becomes [1, 2, 3, 3, 4, 5].
     • Teams can be formed by pairing: (1, 5), (2, 4), and (3, 3).
     • The sum of each team is 6 (i.e. 1+5=6, 2+4=6, 3+3=6).
     • The sum of products is: 1*5 + 2*4 + 3*3 = 5 + 8 + 9 = 22.
   • Output: 22

2. Example 2:

   • Input: [1, 1, 2, 3]
   • Process:
     • Sorted array: [1, 1, 2, 3].
     • Pairing the smallest with the largest gives (1, 3) with a sum of 4.
     • The remaining pair is (1, 2) with a sum of 3, which does not match the first pair’s sum.
   • Output: -1

3. Example 3:

   • Input: [1, 2]
   • Process:
     • Only one pair exists: (1, 2) with a sum of 3.
     • The product is 1 * 2 = 2.
   • Output: 2

Constraints:

• The number of players (i.e. the length of skill) is even.
• ( 2 \leq \text{skill.length} \leq 10^5 )
• Each element in skill is a positive integer.

Hints to Approach the Problem

• Hint 1:
  Think about pairing the smallest and largest players together. If the teams are to have equal total skills, then the sum of the smallest and largest elements should be the same as the sum of the second smallest and second largest, and so on.

• Hint 2:
  Sorting the array can help you quickly form these pairs. Once sorted, determine a target sum using the first and last elements. Then, iterate over the pairs (first with last, second with second last, etc.) and verify that each pair’s sum equals the target. Simultaneously, calculate the sum of the products of the pairs.

Approaches

Approach 1: Brute Force (Conceptual Discussion)

• Idea:
  Try all possible ways to pair the players and check if every team’s sum is equal. Then, calculate the sum of the products for each valid configuration.

• Downside:
  With ( n ) players, the number of ways to pair them grows factorially. This approach quickly becomes computationally intractable for large inputs.

Approach 2: Sorting and Greedy Pairing (Optimal)

• Idea:

  1. Sort the Array:
     Sorting the array makes it easier to form pairs.

  2. Determine the Target Sum:
     Use the sum of the smallest and largest element (i.e. skill[0] + skill[n-1]) as the target sum that every pair must reach.

  3. Pair and Validate:
     Pair the first element with the last, the second with the second-last, and so on. For each pair, check if their sum equals the target sum.

  4. Calculate the Sum of Products:
     If all pairs have the same sum, accumulate the product of the two numbers in each pair.

• Why It’s Optimal:
  Sorting takes (O(n \log n)) and the pairing check takes (O(n)). This approach meets the problem’s constraints even for large inputs.

Approach 3: Alternative – Using Frequency Counting (Less Straightforward)

• Idea:
  One might try to use a frequency count (or hash map) to determine possible pairings, but this approach becomes complex and less intuitive than sorting. The sorting method is both simpler and efficient.

Python Code