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.
This approach involves first sorting the skill array. The goal is to form teams such that each team has an equal total skill value.
By sorting the skills, the smallest and largest unpaired skills can be paired together to potentially form a valid team. This creates a straightforward method to iterate and compare pairs using two pointers, ensuring each team's total skill is consistent.
Utilize two pointers, one starting at the beginning of the sorted skills and the other at the end, to form teams by incrementing or decrementing as conditions require. Check if teams formed balance the array accurately for equal skill sums.
The given C code sorts the array and checks if each pair of smallest and largest skill elements add up to the same total skill value. It uses two pointers to iterate and compute the sum of chemistries.
Time Complexity: O(n log n), due to the sorting step.
Space Complexity: O(1), as no additional space proportional to input size is used.
To solve the problem efficiently without sorting, utilize a hash map to count the frequency of each skill level. By arranging teams based on these frequencies, we can potentially balance skill totals across teams, verifying team chemistry conditions in the progress.
Each team should combine players of differing skill values such that their sum remains consistent each time. This involves iterating across the hash map keys and determining corresponding partners for forming valid teams.
The C solution uses a frequency array to count occurrences of each skill level. It finds valid pairings, checking if skills can sum up consistently. Chemistry is calculated by multiplying paired skill values, adjusting the frequency in-place.
Time Complexity: O(n + k^2), where n is the number of skills and k is the unique skills' range.
Space Complexity: O(k), because of the frequency array for skills up to 1000.
To make all 2-person teams have equal skill points, the minimum value must match the maximum value. Therefore, we sort the skill array, and then use two pointers i and j to point to the beginning and end of the array respectively, match them in pairs, and judge whether their sum is the same number.
If not, it means that the skill points cannot be equal, and we directly return -1. Otherwise, we add the chemical reaction to the answer.
At the end of the traversal, we return the answer.
The time complexity is O(n times log n), and the space complexity is O(log n). Where n is the length of the skill array.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the skill array.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Two-Pointer Technique | Time Complexity: O(n log n), due to the sorting step. |
| Approach 2: Hash Map for Frequency Counting | Time Complexity: O(n + k^2), where n is the number of skills and k is the unique skills' range. |
| Sorting | — |
| Counting | — |
| 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. |
Divide Players Into Teams of Equal Skill - Leetcode 2491 - Python • NeetCodeIO • 9,342 views views
Watch 9 more video solutions →Practice Divide Players Into Teams of Equal Skill with our built-in code editor and test cases.
Practice on FleetCode