2491. Divide Players Into Teams of Equal Skill
Problem Description
In this problem, you are tasked with dividing players with certain skills into teams. The players are represented by a positive integer array called skill
, which has an even number of elements denoted by n
. Each element in the array represents the skill level of a player, with skill[i]
corresponding to the i-th
player's skill.
The players must be divided into n / 2
teams, with each team consisting of two players. The key condition for forming these teams is that the total skill (sum of the skill levels of both team members) must be the same for every team.
The chemistry of a team is defined as the product of the skill levels of the two players in that team. The objective is to calculate and return the sum of the chemistry of all teams. However, if it is impossible to divide the players into teams that all have an equal total skill, you should return -1
.
Intuition
The intuition behind the solution is to first sort the skill
array in increasing order. Sorting is useful because it helps in easily pairing players in such a way that might meet the condition of equal total skill for each team.
After sorting, we set a target total skill value, which is the sum of the first and last element in the sorted array. Considering the array is sorted, this target value should be what we aim to match for each team. We set two pointers, one at the start and one at the end of the sorted array, and start pairing players by moving these pointers towards each other.
At each iteration, we check whether the sum of the skills of the two selected players (pointed by i
and j
) equals the target skill value (t
). If it doesn't match the target, then we know immediately that it's impossible to form the teams with an equal total skill and we return -1
.
If it matches, we compute the chemistry (product of the skills) for this pair of players and add it to a running total (ans
). We then move our pointers inward (increment i
and decrement j
) and continue this process.
We repeat these steps until our pointers meet in the middle. If we are able to pair up all the players in such a way that each team's total skill matches the target, then at the end, we will have successfully found the sum of the chemistry of all teams and return it. If at any point the condition fails, we know that forming the teams as per the condition is not possible, hence the result will be -1
.
Learn more about Two Pointers and Sorting patterns.
Solution Approach
The solution uses a straightforward approach, leveraging sorting and the two-pointer technique to efficiently pair players into teams with equal total skills.
Here's a breakdown of the algorithm:
-
Sorting: The array
skill
is sorted in ascending order. This step ensures that the smallest and largest elements are at the beginning and end of the array, respectively, thus allowing us to easily find pairs that may equal our target total skill. -
Setting a target total skill (
t
): Once sorted, we take the sum of the first (skill[0]
) and last (skill[-1]
) elements to set our target total skill. This forms our baseline which all other pairs must match to ensure all teams have the same total skill. -
Two-Pointer Technique: We use a classic two-pointer approach where one pointer (
i
) starts from the beginning of the array, and the other pointer (j
) starts from the end. We then iterate through the array, with the following steps in our loop:- Check if the sum of the current pair of players (
skill[i] + skill[j]
) equals the target total skill (t
). If not, we immediately return-1
, indicating the task is impossible. - If the pair matches the target, we calculate the chemistry (product) for this team (
skill[i] * skill[j]
) and add it to our running total (ans
). - Move the pointers closer to each other (
i
increments by 1 andj
decrements by 1) to form the next team with the subsequent smallest and largest elements.
- Check if the sum of the current pair of players (
-
Loop until pointers meet: The loop continues until
i
is no longer less thanj
. This means we have checked and formed teams with all players in the sorted array. -
Return the result: If we're able to go through the entire array without finding a mismatch in total skills, we then return the accumulated sum of chemistry (
ans
).
Through this method, we avoid the need for complex data structures and leverage a simple yet effective algorithmic pattern to find the solution. The key to our approach is the greedy strategy of pairing the smallest and largest remaining players to match the target total skill after sorting, ensuring that if there is a possible solution, we will find it.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example to illustrate the solution approach. We have an array skill = [4, 7, 6, 5]
.
-
Sorting: The first step is to sort this array in ascending order. So, after sorting, the array becomes
skill = [4, 5, 6, 7]
. -
Setting a target total skill (
t
): The target total skill is determined by the sum of the first and last elements in the sorted array. Here,t = skill[0] + skill[-1]
which ist = 4 + 7 = 11
. -
Two-Pointer Technique: We set two pointers,
i
at the beginning (i = 0
) andj
at the end (j = 3
). Now, we iterate through the array using these pointers with the following steps:- The sum of the current pair is
skill[i] + skill[j]
, which is4 + 7 = 11
. This equals our targett
. Since the condition is met, we calculate the chemistry for this team, which is4 * 7 = 28
. - We add this chemistry to our running total (
ans
), soans = 28
. - Move the pointers: we increment
i
to1
and decrementj
to2
, and then check the next pair.
- The sum of the current pair is
-
Next Iteration: Now
i = 1
andj = 2
. The sum of this new pair of players isskill[1] + skill[2]
, which is5 + 6 = 11
. Again, this matches our targett
.- The chemistry for this team is
5 * 6 = 30
. - We add it to our running total, so now
ans = 28 + 30 = 58
. - Since we have no more elements left to pair, we have reached the end of our iteration.
- The chemistry for this team is
-
Return the result: As we have successfully formed teams such that each team's total skill equals the target total skill, and there were no mismatches, we return the sum of the chemistry of all teams, which is
ans = 58
.
Therefore, for the given example skill = [4, 7, 6, 5]
, the function would return 58
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def dividePlayers(self, skills: List[int]) -> int:
5 # Sort the list of skills in ascending order
6 skills.sort()
7
8 # Calculate the target sum of skills for a pair of players
9 target_sum = skills[0] + skills[-1]
10
11 # Initialize pointers at the beginning and end of the list
12 left, right = 0, len(skills) - 1
13
14 # Initialize variable to store the cumulative product of valid pairs
15 cumulative_product = 0
16
17 # Loop through the skills list using two pointers from both ends towards the center
18 while left < right:
19 # If the current pair of players doesn't have the desired sum, return -1
20 if skills[left] + skills[right] != target_sum:
21 return -1
22
23 # Calculate the product of the current valid pair's skills
24 cumulative_product += skills[left] * skills[right]
25
26 # Move the pointers towards the center for the next potential pair
27 left += 1
28 right -= 1
29
30 # Return the cumulative product of all valid pairs' skills
31 return cumulative_product
32
33# Example usage:
34# solution = Solution()
35# result = solution.dividePlayers([4, 5, 1, 2, 3, 6])
36# print(result) # Output would depend on the logic correctness and input values
37
1class Solution {
2
3 public long dividePlayers(int[] skillLevels) {
4 // Sort the skill levels array to organize players by their skill
5 Arrays.sort(skillLevels);
6
7 // Get the number of players
8 int numOfPlayers = skillLevels.length;
9
10 // Calculate the target sum based on the lowest and highest skill levels
11 int targetSum = skillLevels[0] + skillLevels[numOfPlayers - 1];
12
13 // Initialize the answer variable to store the sum of products
14 long answer = 0;
15
16 // Use two pointers to iterate from the beginning and end towards the center
17 for (int left = 0, right = numOfPlayers - 1; left < right; ++left, --right) {
18 // Check if the current pair of players does not meet the target sum
19 if (skillLevels[left] + skillLevels[right] != targetSum) {
20 return -1; // Return -1 if condition is not met, indicating invalid pairing
21 }
22
23 // Calculate the product of the skill levels of the two players and add it to the answer
24 answer += (long) skillLevels[left] * skillLevels[right];
25 }
26
27 // Return the final answer which is the sum of products of the pairs
28 return answer;
29 }
30}
31
1#include <vector>
2#include <algorithm> // Include algorithm header for sort
3
4class Solution {
5public:
6 long long dividePlayers(vector<int>& skillLevels) {
7 // Sort the skill levels in ascending order
8 sort(skillLevels.begin(), skillLevels.end());
9
10 int numPlayers = skillLevels.size(); // Number of players
11 int teamBalancingFactor = skillLevels[0] + skillLevels[numPlayers - 1];
12 long long productSum = 0; // Variable to store the sum of product of skills
13
14 // Pair players starting from the weakest and the strongest
15 for (int left = 0, right = numPlayers - 1; left < right; ++left, --right) {
16 // If the pair doesn't add up to the balancing factor, teams can't be balanced
17 if (skillLevels[left] + skillLevels[right] != teamBalancingFactor) {
18 return -1;
19 }
20 // Add up product of the skills of the two players
21 productSum += static_cast<long long>(skillLevels[left]) * skillLevels[right];
22 }
23
24 // Return the total sum of products of the skills for all pairs
25 return productSum;
26 }
27};
28
1function dividePlayers(skillLevels: number[]): number {
2 // Determine the number of players
3 const numOfPlayers = skillLevels.length;
4
5 // Sort the skillLevels in ascending order
6 skillLevels.sort((a, b) => a - b);
7
8 // Set target sum as the sum of the lowest and highest skill levels
9 const targetSum = skillLevels[0] + skillLevels[numOfPlayers - 1];
10
11 // Initialize answer variable to store the product sum
12 let productSum = 0;
13
14 // Iterate over the first half of the sorted array
15 for (let i = 0; i < numOfPlayers / 2; i++) {
16 // Check if the current pair does not sum up to the target sum
17 if (targetSum !== skillLevels[i] + skillLevels[numOfPlayers - 1 - i]) {
18 // If they don't, pairing is not possible, return -1
19 return -1;
20 }
21
22 // Accumulate the products of the pair into the productSum
23 productSum += skillLevels[i] * skillLevels[numOfPlayers - 1 - i];
24 }
25
26 // Return the final product sum as the answer
27 return productSum;
28}
29
Time and Space Complexity
The time complexity of the dividePlayers
function is primarily determined by the sort operation. In Python, the sort method typically uses Timsort, an algorithm with a time complexity of O(n log n)
, where n
is the number of elements in the input list skill
. Once the list is sorted, the function enters a while-loop, which iterates approximately n/2
times (since each iteration pairs up one element from the start of the list with one from the end). The operations inside the loop are constant time operations, so they do not add more than O(n)
to the time complexity. As a result, the overall time complexity of the function is dominated by the sorting step: O(n log n)
.
For space complexity, the code does not create any additional data structures that grow with the size of the input list; it only uses a fixed number of variables. Therefore, the space complexity is O(1)
, implying constant space usage excluding the input list.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]
?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
8
1public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
12
1class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.