2491. Divide Players Into Teams of Equal Skill

MediumArrayHash TableTwo PointersSorting

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 and j decrements by 1) to form the next team with the subsequent smallest and largest elements.
Loop until pointers meet: The loop continues until i is no longer less than j. 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 Evaluator

Example 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 is t = 4 + 7 = 11.
Two-Pointer Technique: We set two pointers, i at the beginning (i = 0) and j 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 is 4 + 7 = 11. This equals our target t. Since the condition is met, we calculate the chemistry for this team, which is 4 * 7 = 28.
- We add this chemistry to our running total (ans), so ans = 28.
- Move the pointers: we increment i to 1 and decrement j to 2, and then check the next pair.
Next Iteration: Now i = 1 and j = 2. The sum of this new pair of players is skill[1] + skill[2], which is 5 + 6 = 11. Again, this matches our target t.
- 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.
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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: