Skip to main content
Talentd

Divide Players Into Teams of Equal Skill - Solution & Explanation

MediumArrayHash TableTwo PointersSorting25 min readAsked at: Amazon, Microsoft, Visa +3
Practice this problem

Problem Statement

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

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Sorting and Two-Pointer Technique

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.

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.
Space Complexity: O(k), because of the frequency array for skills up to 1000.

Sorting—
Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting + Two PointersO(n log n)O(1) auxiliaryMost common interview approach. Simple logic after sorting and easy to verify valid pair sums.
Hash Map Frequency CountingO(n)O(n)Best when avoiding sorting. Useful for large inputs where linear-time pairing with complement lookup is preferred.

Video Solution

Divide Players Into Teams of Equal Skill - Leetcode 2491 - Python • NeetCodeIO • 9,503 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Divide Players Into Teams of Equal Skill with our built-in code editor and test cases.

Practice on FleetCode
Previous

Max Number of K-Sum Pairs

Next

Minimum Moves to Equal Array Elements