Divide Players Into Teams of Equal Skill
MedPrompt
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.lengthis even.1 <= skill[i] <= 1000
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Iterate through each player
skill[i](wherei > 0) to be a potential partner for the first player,skill[0]. - For each
i, define a potential target sum for all teams:target_sum = skill[0] + skill[i]. - Create a frequency map of all skills in the input array to count occurrences of each skill value.
- For the current
target_sum, attempt to partition all players inton/2teams. This can be done by iterating through the skills and their counts in the frequency map. - For each skill
kin the map, its required partner isp = target_sum - k. Check ifpexists in the map with a sufficient count. - If
k == p, the count ofkmust be even. Ifk != p, the count ofkmust equal the count ofp. - If a valid partner cannot be found for any skill, this
target_sumis invalid. Break and try the nexttarget_sum. - If all players can be paired up successfully, calculate the total chemistry and return it.
- If the main loop finishes without finding any valid
target_sum, it's impossible to partition the players as required. Return -1.
Walkthrough
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; }}Complexity
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.
Trade-offs
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 (nup 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.
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.