Divide Players Into Teams of Equal Skill solution and explanation
9 more videos on this problem
Divide Players Into Teams of Equal Skill - Leetcode 2491 - PythonNeetCodeIO · 8:26 · 9K views
Divide Players Into Teams of Equal Skill | Leetcode 2491Techdose · 16:50 · 1K views
2491. Divide Players Into Teams of Equal Skill (Leetcode Medium)Programming Live with Larry · 10:50 · 506 views
Leetcode 2491 Divide Players Into Teams of Equal Skill (Java) - Leetcode Contest 322TheAnalyticGuy · 6:55 · 367 views
Divide Players Into Teams of Equal Skill - HashMap - PythonCheatCode Ninja · 5:35 · 298 views
[LeetCode-Weekly-322] 2491. Divide Players Into Teams of Equal SkillSandeep Kumar · 11:52 · 187 views
Leetcode: 2491. Divide Players Into Teams of Equal Skill with explanations, typescriptYou code with Dmytro · 5:05 · 170 views
Leetcode 2491 | Divide Players Into Teams of Equal Skill | FastestJeevan Kumar - Cracckify · 6:15 · 89 views
Leetcode 2491 Divide Players Into Teams of Equal SkillMath Geeks · 2:45 · 58 views
Leetcode 2491. Divide Players Into Teams of Equal SkillElite Code · 28:04 · 46 views
The 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 <= 105skill.lengthis even.1 <= skill[i] <= 1000
Approach overview
Problem 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 1: Approach 1: Sorting and Two-Pointer Technique
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.
def team_chemistry(skill):
skill.sort()
left, right = 0, len(skill) - 1
total_skill = skill[left] + skill[right]
chemistry_sum = 0
while left < right:
if skill[left] + skill[right] != total_skill:
return -1
chemistry_sum += skill[left] * skill[right]
left += 1
right -= 1
return chemistry_sum
# Test example
skill = [3, 2, 5, 1, 3, 4]
print(team_chemistry(skill))import java.util.Arrays;
public class TeamChemistry {
public static int teamChemistry(int[] skill) {
Arrays.sort(skill);
int left = 0, right = skill.length - 1;
int totalSkill = skill[left] + skill[right];
int chemistrySum = 0;
while (left < right) {
if (skill[left] + skill[right] != totalSkill) return -1;
chemistrySum += skill[left] * skill[right];
left++;
right--;
}
return chemistrySum;
}
public static void main(String[] args) {
int[] skill = {3, 2, 5, 1, 3, 4};
System.out.println(teamChemistry(skill));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int teamChemistry(std::vector<int>& skill) {
std::sort(skill.begin(), skill.end());
int totalSkill = skill.front() + skill.back();
int chemistrySum = 0;
int left = 0, right = skill.size() - 1;
while (left < right) {
if (skill[left] + skill[right] != totalSkill) return -1;
chemistrySum += skill[left] * skill[right];
++left;
--right;
}
return chemistrySum;
}
int main() {
std::vector<int> skill = {3, 2, 5, 1, 3, 4};
std::cout << teamChemistry(skill) << std::endl;
return 0;
}function teamChemistry(skill) {
skill.sort((a, b) => a - b);
let left = 0;
let right = skill.length - 1;
const totalSkill = skill[left] + skill[right];
let chemistrySum = 0;
while (left < right) {
if (skill[left] + skill[right] !== totalSkill) return -1;
chemistrySum += skill[left] * skill[right];
left++;
right--;
}
return chemistrySum;
}
const skill = [3, 2, 5, 1, 3, 4];
console.log(teamChemistry(skill));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int teamChemistry(int* skill, int skillSize) {
qsort(skill, skillSize, sizeof(int), compare);
int left = 0, right = skillSize - 1;
int totalSkill = skill[left] + skill[right];
int chemistrySum = 0;
while (left < right) {
if (skill[left] + skill[right] != totalSkill) return -1;
chemistrySum += skill[left] * skill[right];
left++;
right--;
}
return chemistrySum;
}
int main() {
int skill[] = {3, 2, 5, 1, 3, 4};
int skillSize = sizeof(skill) / sizeof(skill[0]);
printf("%d\n", teamChemistry(skill, skillSize));
return 0;
}using System;
class TeamChemistryClass {
public static int TeamChemistry(int[] skill) {
Array.Sort(skill);
int left = 0, right = skill.Length - 1;
int totalSkill = skill[left] + skill[right];
int chemistrySum = 0;
while (left < right) {
if (skill[left] + skill[right] != totalSkill) return -1;
chemistrySum += skill[left] * skill[right];
left++;
right--;
}
return chemistrySum;
}
static void Main() {
int[] skill = { 3, 2, 5, 1, 3, 4 };
Console.WriteLine(TeamChemistry(skill));
}
}This Python version sorts the skill array and uses two pointers to determine if each pair of players can consistently be grouped to keep cumulative team skills equal. It adds each product for the chemistry sum if valid.
Time Complexity: O(n log n), mainly from sorting.
Space Complexity: O(1), due to in-place computation and pointer navigation.
Approach 2: Approach 2: Hash Map for Frequency Counting
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.
from collections import Counter
def team_chemistry(skill):
freq = Counter(skill)
total_skill = None
chemistry_sum = 0
for i in list(freq):
while freq[i] > 0:
for j in range(i, 1001):
if freq[j] > 0:
skill_sum = i + j
if total_skill is None:
total_skill = skill_sum
if skill_sum != total_skill:
return -1
chemistry_sum += i * j
freq[i] -= 1
freq[j] -= 1
return chemistry_sum
# Test example
skill = [3, 2, 5, 1, 3, 4]
print(team_chemistry(skill))import java.util.HashMap;
public class TeamChemistry {
public static int teamChemistry(int[] skill) {
HashMap<Integer, Integer> freq = new HashMap<>();
for (int i : skill) {
freq.put(i, freq.getOrDefault(i, 0) + 1);
}
Integer totalSkill = null;
int chemistrySum = 0;
for (int i : freq.keySet()) {
while (freq.get(i) > 0) {
for (int j = i; j <= 1000; j++) {
if (freq.containsKey(j) && freq.get(j) > 0) {
int skillSum = i + j;
if (totalSkill == null) {
totalSkill = skillSum;
}
if (skillSum != totalSkill) return -1;
chemistrySum += i * j;
freq.put(i, freq.get(i) - 1);
freq.put(j, freq.get(j) - 1);
}
}
}
}
return chemistrySum;
}
public static void main(String[] args) {
int[] skill = {3, 2, 5, 1, 3, 4};
System.out.println(teamChemistry(skill));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
int teamChemistry(std::vector<int>& skill) {
std::unordered_map<int, int> freq;
for (int s : skill) {
freq[s]++;
}
int totalSkill = -1, chemistrySum = 0;
for (const auto& entry : freq) {
int i = entry.first;
while (freq[i] > 0) {
for (int j = i; j <= 1000; j++) {
if (freq[j] > 0) {
int skillSum = i + j;
if (totalSkill == -1) {
totalSkill = skillSum;
}
if (skillSum != totalSkill) return -1;
chemistrySum += i * j;
freq[i]--;
freq[j]--;
}
}
}
}
return chemistrySum;
}
int main() {
std::vector<int> skill = {3, 2, 5, 1, 3, 4};
std::cout << teamChemistry(skill) << std::endl;
return 0;
}function teamChemistry(skill) {
const freq = {};
skill.forEach(s => freq[s] = (freq[s] || 0) + 1);
let totalSkill = null, chemistrySum = 0;
for (let i in freq) {
i = parseInt(i);
while (freq[i] > 0) {
for (let j = i; j <= 1000; j++) {
if (freq[j] > 0) {
const skillSum = i + j;
if (totalSkill === null) totalSkill = skillSum;
if (skillSum !== totalSkill) return -1;
chemistrySum += i * j;
freq[i]--;
freq[j]--;
break;
}
}
}
}
return chemistrySum;
}
const skill = [3, 2, 5, 1, 3, 4];
console.log(teamChemistry(skill));#include <stdio.h>
#include <string.h>
#define MAX_SKILL 1000
int teamChemistry(int* skill, int skillSize) {
int freq[MAX_SKILL + 1] = {0};
for (int i = 0; i < skillSize; i++) {
freq[skill[i]]++;
}
int totalSkill = -1, chemistrySum = 0;
for (int i = 1; i <= MAX_SKILL; i++) {
if (freq[i] > 0) {
for (int j = i; j <= MAX_SKILL; j++) {
while (freq[i] > 0 && freq[j] > 0) {
int skillSum = i + j;
if (totalSkill == -1) {
totalSkill = skillSum;
}
if (skillSum != totalSkill) return -1;
chemistrySum += i * j;
freq[i]--;
freq[j]--;
}
}
}
}
return chemistrySum;
}
int main() {
int skill[] = {3, 2, 5, 1, 3, 4};
int skillSize = sizeof(skill) / sizeof(skill[0]);
printf("%d\n", teamChemistry(skill, skillSize));
return 0;
}using System;
using System.Collections.Generic;
class TeamChemistryClass {
public static int TeamChemistry(int[] skill) {
Dictionary<int, int> freq = new Dictionary<int, int>();
foreach (var s in skill) {
if (!freq.ContainsKey(s)) freq[s] = 0;
freq[s]++;
}
int? totalSkill = null;
int chemistrySum = 0;
foreach (var i in freq.Keys) {
while (freq[i] > 0) {
for (int j = i; j <= 1000; j++) {
if (freq.ContainsKey(j) && freq[j] > 0) {
int skillSum = i + j;
if (totalSkill == null) {
totalSkill = skillSum;
}
if (skillSum != totalSkill) return -1;
chemistrySum += i * j;
freq[i]--;
freq[j]--;
}
}
}
}
return chemistrySum;
}
static void Main() {
int[] skill = { 3, 2, 5, 1, 3, 4 };
Console.WriteLine(TeamChemistry(skill));
}
}The Python code employs a Counter (hash map equivalent) to register the skill frequencies. It forms balanced team pairs by iterating across skill levels, ensuring consistency through paired products for chemistry sum computation.
Time Complexity: O(n + k^2), due to potentially traversing all skill pairs.
Space Complexity: O(k), where k is the range of skill values forming entries in the Counter.
Approach 3: Sorting
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.
function dividePlayers(skill: number[]): number {
const n = skill.length;
skill.sort((a, b) => a - b);
const target = skill[0] + skill[n - 1];
let ans = 0;
for (let i = 0; i < n >> 1; i++) {
if (target !== skill[i] + skill[n - 1 - i]) {
return -1;
}
ans += skill[i] * skill[n - 1 - i];
}
return ans;
}func dividePlayers(skill []int) (ans int64) {
sort.Ints(skill)
n := len(skill)
t := skill[0] + skill[n-1]
for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
if skill[i]+skill[j] != t {
return -1
}
ans += int64(skill[i] * skill[j])
}
return
}impl Solution {
pub fn divide_players(mut skill: Vec<i32>) -> i64 {
let n = skill.len();
skill.sort();
let target = skill[0] + skill[n - 1];
let mut ans = 0;
for i in 0..n >> 1 {
if skill[i] + skill[n - 1 - i] != target {
return -1;
}
ans += (skill[i] * skill[n - 1 - i]) as i64;
}
ans
}
}Approach 4: Counting
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the skill array.
function dividePlayers(skill: number[]): number {
let [sum, res, map] = [0, 0, new Map<number, number>()];
for (const x of skill) {
sum += x;
map.set(x, (map.get(x) || 0) + 1);
}
sum /= skill.length / 2;
for (let [x, c] of map) {
const complement = sum - x;
if ((map.get(complement) ?? 0) !== c) return -1;
if (x === complement) c /= 2;
res += x * complement * c;
map.delete(x);
map.delete(complement);
}
return res;
}func dividePlayers(skill []int) int64 {
s := 0
for _, v := range skill {
s += v
}
m := len(skill) >> 1
if s%m != 0 {
return -1
}
t := s / m
d := [1010]int{}
ans := 0
for _, v := range skill {
if d[t-v] > 0 {
ans += v * (t - v)
d[t-v]--
m--
} else {
d[v]++
}
}
if m == 0 {
return int64(ans)
}
return -1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Two-Pointer Technique | Time Complexity: O(n log n), mainly from sorting. |
| Approach 2: Hash Map for Frequency Counting | Time Complexity: O(n + k^2), due to potentially traversing all skill pairs. |
| Sorting | – |
| Counting | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Divide Players Into Teams of Equal Skill easy or hard?
The problem is rated Medium because it requires recognizing the invariant that every pair must share the same total skill. Once that observation is clear, the solution reduces to pairing elements using sorting or hash map complements. The implementation itself is straightforward but the pairing insight is the key step.
Divide Players Into Teams of Equal Skill Python/Java solution
Python and Java implementations typically follow either sorting with two pointers or a hash map counting approach. After determining the required pair sum, iterate through pairs and accumulate chemistry using multiplication of skill values. Both languages implement this in a few lines once the pairing logic is established.
How to solve Divide Players Into Teams of Equal Skill in O(n)?
Use a hash map to count the frequency of each skill value. Compute the required pair sum using totalSkill divided by the number of teams. For each player skill, check whether the complement (target - skill) exists in the map and reduce counts when forming a pair. Each lookup and update is constant time, giving an overall O(n) solution.
What is the best approach for Divide Players Into Teams of Equal Skill?
The most common solution sorts the skill array and uses a two-pointer technique. Pair the smallest and largest players and verify that every pair produces the same total skill. This approach runs in O(n log n) time due to sorting and uses O(1) extra space. It is widely expected in interviews because the logic is simple and easy to validate.
Is Divide Players Into Teams of Equal Skill asked at Google/Amazon/Meta?
Problems involving pairing elements to reach a fixed sum frequently appear in interviews at companies like Amazon, Google, and Meta. Variants test understanding of sorting, two-pointer strategies, and hash map complement searches. This problem combines both patterns and is representative of medium-level array questions.
What data structure is used in Divide Players Into Teams of Equal Skill?
Two main techniques appear in solutions. The sorting approach relies on arrays and the two-pointer pattern after sorting. The optimized approach uses a hash map (frequency table) to quickly find complementary skill values needed to form valid teams.
What is the time complexity of Divide Players Into Teams of Equal Skill?
The sorting-based solution runs in O(n log n) time because of the sorting step, followed by a linear two-pointer scan. A hash map optimization can solve the problem in O(n) time by counting skill frequencies and pairing complements directly. Space complexity is O(1) for the sorting approach or O(n) for the hash map.