Watch 10 video solutions for Divide Players Into Teams of Equal Skill, a medium level problem involving Array, Hash Table, Two Pointers. This walkthrough by NeetCodeIO has 9,342 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105skill.length is even.1 <= skill[i] <= 1000Problem Overview: You are given an array where each value represents a player's skill. The task is to divide players into pairs so every team has the same total skill. If such pairing is possible, return the sum of each team's chemistry (product of the two skills). Otherwise return -1.
Approach 1: Sorting and Two-Pointer Technique (Time: O(n log n), Space: O(1) or O(log n) depending on sorting)
Sort the skill array and try pairing the smallest and largest remaining players. After sorting, the only way to keep team skill sums consistent is if skill[left] + skill[right] equals the same target for every pair. Initialize the target using the first and last elements, then move two pointers inward while checking this condition. If any pair breaks the rule, forming equal-skill teams is impossible. For each valid pair, accumulate chemistry using skill[left] * skill[right]. Sorting guarantees deterministic pairing and keeps the implementation simple. This approach commonly appears in problems involving sorting and two pointers.
Approach 2: Hash Map for Frequency Counting (Time: O(n), Space: O(n))
This method avoids sorting by counting how many players have each skill using a hash map. First compute the required team sum. If players must form n/2 teams with equal skill, the total skill of all players must be divisible by the number of teams. The required pair sum becomes totalSkill / (n/2). Iterate through each player and check whether the complementary skill target - skill[i] exists in the frequency map. If available, form a pair, decrement counts, and add the chemistry contribution. If the complement is missing, pairing is impossible. Hash lookups make each operation constant time, which leads to linear complexity. This technique relies on a hash table for fast complement lookup.
Recommended for interviews: The sorting + two-pointer approach is the most common answer because it is easy to reason about and implement quickly. It clearly demonstrates understanding of pairing strategies after sorting. The hash map approach shows deeper optimization and achieves O(n) time, which is useful when sorting overhead matters. Showing both approaches signals strong algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Two Pointers | O(n log n) | O(1) auxiliary | Most common interview approach. Simple logic after sorting and easy to verify valid pair sums. |
| Hash Map Frequency Counting | O(n) | O(n) | Best when avoiding sorting. Useful for large inputs where linear-time pairing with complement lookup is preferred. |