# Divide Players Into Teams of Equal Skill
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/divide-players-into-teams-of-equal-skill)
Canonical: https://scaleengineer.com/dsa/problems/divide-players-into-teams-of-equal-skill
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Expedia](https://scaleengineer.com/companies/expedia), [IBM](https://scaleengineer.com/companies/ibm), [PayPal](https://scaleengineer.com/companies/paypal)
---
## 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._

**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`

# Approaches
## Brute Force with Frequency Map
The core idea of this brute-force approach is to systematically try every possible valid target sum for the teams. A potential target sum can be determined by picking a fixed player, say `skill[0]`, and pairing them with every other player, `skill[i]`. This generates `n-1` candidate target sums.

For each candidate `target_sum`, we then verify if it's possible to partition all `n` players into `n/2` teams, where each team's skill sum equals this `target_sum`. To do this check efficiently, we use a frequency map (e.g., a `HashMap`) to count the occurrences of each skill. We then iterate through our map, and for each skill `k`, we check if its required partner `(target_sum - k)` exists in the map with the necessary frequency. If we can successfully pair up all players for a given `target_sum`, we calculate the total chemistry and return it. If we exhaust all `n-1` possibilities without success, no solution exists.
**Time:** O(n^2). The outer loop runs `n-1` times to select a partner for `skill[0]`. Inside this loop, we build a frequency map (`O(n)`) and then iterate through the skills again to check for pairs (`O(n)`), resulting in a quadratic time complexity. · **Space:** O(K) or O(n), where K is the number of unique skills. A frequency map is used to store skill counts. In the worst case, all `n` skills are unique, leading to `O(n)` space.
**Pros:** It's a straightforward brute-force method that explores all possibilities stemming from the first player's pairing.; It does not require modifying the original input array (no sorting).
**Cons:** The time complexity of `O(n^2)` is too slow for the given constraints (`n` up to 10^5), leading to a 'Time Limit Exceeded' error on larger test cases.; The implementation is more complex than the optimal solution, involving nested loops and careful management of the frequency map.
### Explanation
```java
import java.util.Map;
import java.util.HashMap;

class Solution {
    public long dividePlayers(int[] skill) {
        int n = skill.length;
        if (n % 2 != 0) {
            return -1;
        }

        // Try every other player as a partner for skill[0]
        for (int i = 1; i < n; i++) {
            long targetSum = skill[0] + skill[i];
            
            Map<Integer, Integer> freq = new HashMap<>();
            for (int s : skill) {
                freq.put(s, freq.getOrDefault(s, 0) + 1);
            }

            long currentChemistry = 0;
            boolean possible = true;

            for (int s : skill) {
                // If skill s has already been paired, its count will be 0
                if (freq.getOrDefault(s, 0) > 0) {
                    int partnerSkill = (int) (targetSum - s);
                    
                    // Decrement current skill's count
                    freq.put(s, freq.get(s) - 1);

                    // Check for partner
                    if (freq.getOrDefault(partnerSkill, 0) > 0) {
                        freq.put(partnerSkill, freq.get(partnerSkill) - 1);
                        currentChemistry += (long) s * partnerSkill;
                    } else {
                        // No partner found, this targetSum is not possible
                        possible = false;
                        break;
                    }
                }
            }

            if (possible) {
                // Each pair's chemistry was added twice (once for s, once for partner)
                return currentChemistry / 2;
            }
        }

        return -1;
    }
}
```
### Algorithm
1. Iterate through each player `skill[i]` (where `i > 0`) to be a potential partner for the first player, `skill[0]`.
2. For each `i`, define a potential target sum for all teams: `target_sum = skill[0] + skill[i]`.
3. Create a frequency map of all skills in the input array to count occurrences of each skill value.
4. For the current `target_sum`, attempt to partition all players into `n/2` teams. This can be done by iterating through the skills and their counts in the frequency map.
5. For each skill `k` in the map, its required partner is `p = target_sum - k`. Check if `p` exists in the map with a sufficient count.
6. If `k == p`, the count of `k` must be even. If `k != p`, the count of `k` must equal the count of `p`.
7. If a valid partner cannot be found for any skill, this `target_sum` is invalid. Break and try the next `target_sum`.
8. If all players can be paired up successfully, calculate the total chemistry and return it.
9. If the main loop finishes without finding any valid `target_sum`, it's impossible to partition the players as required. Return -1.

## Sorting and Two Pointers
A much more efficient approach relies on a key insight: if a valid set of teams can be formed, the player with the lowest skill must be paired with the player with the highest skill. Why? If the lowest-skill player were paired with anyone else, the highest-skill player would need a partner with a skill lower than the minimum possible skill to match the team sum, which is a contradiction.

This logic extends inwards. After pairing the lowest and highest, the second-lowest must be paired with the second-highest, and so on. This leads to a simple and elegant algorithm. First, we sort the `skill` array. Then, we use a two-pointer technique. One pointer starts at the beginning (`left`), and the other at the end (`right`). We check if `skill[left] + skill[right]` is constant for all pairs as we move the pointers towards the center. If it is, we sum up the chemistries; otherwise, no solution exists.
**Time:** O(n log n). The time complexity is dominated by the initial sorting of the `skill` array. The subsequent two-pointer scan runs in `O(n)` time. · **Space:** O(log n) to O(n). The space complexity depends on the implementation of the sorting algorithm. In Java, `Arrays.sort` for primitives uses a variant of Quicksort, which requires `O(log n)` space on average for the recursion stack, and `O(n)` in the worst case.
**Pros:** Highly efficient with `O(n log n)` time complexity, which passes all constraints.; The logic is simple to understand and implement.; It is guaranteed to find the unique valid pairing if one exists.
**Cons:** The `O(n log n)` time complexity is determined by the sorting step. While very good, it's technically not linear time.; The approach requires modifying the input array by sorting it. If the original order must be preserved, a copy of the array should be made first, which would use `O(n)` extra space.
### Explanation
```java
import java.util.Arrays;

class Solution {
    public long dividePlayers(int[] skill) {
        int n = skill.length;
        // Sort the array to easily pair lowest with highest skill players
        Arrays.sort(skill);

        // The target sum for each team is determined by the first and last elements
        long targetSum = skill[0] + skill[n - 1];
        long totalChemistry = 0;

        // Use two pointers to form teams from the ends of the sorted array
        int left = 0;
        int right = n - 1;

        while (left < right) {
            // Check if the current pair has the required sum
            if (skill[left] + skill[right] != targetSum) {
                return -1; // If not, a valid division is impossible
            }

            // Add the chemistry of the current team to the total
            totalChemistry += (long) skill[left] * skill[right];

            // Move to the next pair
            left++;
            right--;
        }

        return totalChemistry;
    }
}
```
### Algorithm
1. Sort the `skill` array in non-decreasing order.
2. The player with the minimum skill is now at `skill[0]` and the maximum is at `skill[n-1]`. If a solution exists, they must be paired together. Their sum defines the single possible target sum for all teams: `target_sum = skill[0] + skill[n-1]`.
3. Initialize two pointers: `left` at the start of the array (index 0) and `right` at the end (index `n-1`).
4. Initialize a variable `total_chemistry` to 0.
5. Loop while `left < right`:
   a. Check if the sum of the skills at the pointers, `skill[left] + skill[right]`, equals `target_sum`.
   b. If the sum is not equal to `target_sum`, a valid division is impossible. Return -1.
   c. If the sum is equal, this is a valid team. Add their chemistry, `(long)skill[left] * skill[right]`, to `total_chemistry`.
   d. Move the pointers inwards to consider the next pair: `left++` and `right--`.
6. If the loop completes, all players have been successfully paired. Return `total_chemistry`.

## Counting Sort and Two Pointers
This approach is a further optimization of the sorting-based method. Given the constraint that skill values are in a limited range (1 to 1000), we can replace the `O(n log n)` comparison-based sort with a linear time sorting algorithm like Counting Sort. This improves the overall time complexity to be linear.

First, we create a frequency array to count the occurrences of each skill value. This takes `O(n + K)` time, where `K` is the range of skills. Then, instead of using pointers on a sorted array, we use pointers on the frequency array itself to find the current minimum and maximum available skills to pair. We repeatedly pair the smallest available skill with the largest available skill, check if their sum matches the target, and accumulate the chemistry. This avoids the `log n` factor from sorting, making it the most efficient solution.
**Time:** O(n + K). Populating the frequency array takes `O(n)`. The main loop runs `n/2` times, and the two pointers (`left` and `right`) together traverse the range of skills `K` at most once. Thus, the total time is linear. · **Space:** O(K), where `K` is the range of skill values (1000). We use an auxiliary `counts` array of size `K+1`. Since `K` is a constant, this is considered `O(1)` space.
**Pros:** Achieves the best possible time complexity of `O(n + K)`, which is linear.; Space complexity is constant with respect to `n`, as it only depends on the fixed range of skill values (`K`).
**Cons:** This approach is specialized. Its efficiency relies on the constraint that skill values fall within a small, fixed range. It would not be efficient if the skill values could be arbitrarily large.
### Explanation
```java
class Solution {
    public long dividePlayers(int[] skill) {
        int n = skill.length;
        int MAX_SKILL = 1000;
        int[] counts = new int[MAX_SKILL + 1];
        int minSkill = Integer.MAX_VALUE;
        int maxSkill = Integer.MIN_VALUE;

        for (int s : skill) {
            counts[s]++;
            minSkill = Math.min(minSkill, s);
            maxSkill = Math.max(maxSkill, s);
        }

        long targetSum = minSkill + maxSkill;
        long totalChemistry = 0;

        int left = minSkill;
        int right = maxSkill;

        // We need to form n/2 teams
        for (int i = 0; i < n / 2; i++) {
            // Find the next available smallest skill
            while (counts[left] == 0) {
                left++;
            }
            // Find the next available largest skill
            while (counts[right] == 0) {
                right--;
            }

            // Check if this pair matches the target sum
            if (left + right != targetSum) {
                return -1;
            }

            // Add chemistry and "use up" the players for this team
            totalChemistry += (long) left * right;
            counts[left]--;
            counts[right]--;
        }

        return totalChemistry;
    }
}
```
### Algorithm
1. Since skill values are bounded (`1 <= skill[i] <= 1000`), we can use a non-comparison sort. Create a frequency array, `counts`, of size 1001.
2. Iterate through the input `skill` array once to populate the `counts` array and simultaneously find the minimum (`minSkill`) and maximum (`maxSkill`) skill values present.
3. The target sum for all teams is fixed: `target_sum = minSkill + maxSkill`.
4. Initialize `total_chemistry` to 0.
5. Loop `n/2` times to form the `n/2` teams.
   a. In each iteration, we need to find the current smallest available skill and the current largest available skill. We can use two pointers, `left` and `right`, starting at `minSkill` and `maxSkill` respectively.
   b. Advance the `left` pointer until it finds a skill `l` where `counts[l] > 0`.
   c. Advance the `right` pointer until it finds a skill `r` where `counts[r] > 0`.
   d. Check if `l + r` equals `target_sum`. If not, return -1.
   e. If they match, form a team. Add their chemistry `(long)l * r` to `total_chemistry`.
   f. Decrement the counts for these two skills: `counts[l]--` and `counts[r]--`.
6. After the loop finishes, return `total_chemistry`.

# Solutions
### Java

```java
class Solution {
public
  long dividePlayers(int[] skill) {
    Arrays.sort(skill);
    int n = skill.length;
    int t = skill[0] + skill[n - 1];
    long ans = 0;
    for (int i = 0, j = n - 1; i < j; ++i, --j) {
      if (skill[i] + skill[j] != t) {
        return -1;
      }
      ans += (long)skill[i] * skill[j];
    }
    return ans;
  }
}

```

### JavaScript

```javascript
var dividePlayers = function ( skill ) { const n = skill . length , m = n / 2 ; skill . sort (( a , b ) => a - b ); const sum = skill [ 0 ] + skill [ n - 1 ]; let ans = 0 ; for ( let i = 0 ; i < m ; i ++ ) { const x = skill [ i ], y = skill [ n - 1 - i ]; if ( x + y != sum ) return - 1 ; ans += x * y ; } return ans ; };
```

### CPP

```cpp
class Solution { public: long long dividePlayers ( vector < int >& skill ) { sort ( skill . begin (), skill . end ()); int n = skill . size (); int t = skill [ 0 ] + skill [ n - 1 ]; long long ans = 0 ; for ( int i = 0 , j = n - 1 ; i < j ; ++ i , -- j ) { if ( skill [ i ] + skill [ j ] != t ) return - 1 ; ans += 1ll * skill [ i ] * skill [ j ]; } return ans ; } };
```

### Python

```python
class Solution:
    def dividePlayers(self, skill: List[int]) -> int: skill . sort() t = skill[0] + skill[- 1] i, j = 0, len(skill) - 1 ans = 0 while i < j: if skill[i] + skill[j] != t: return - 1 ans += skill[i] * skill[j] i, j = i + 1, j - 1 return ans

```