DDSA Solutions

2491. Divide Players Into Teams of Equal Skill

MediumView on LeetCode
ArrayHash TableTwo PointersGreedySorting
Time: O(n log n)
Space: O(1)

Problem Overview

Divide players into pairs where each pair sums to same value.

Intuition

Divide players into pairs where each pair sums to same value. Sort, pair first with last.

Algorithm

  1. 1Sort. Check all pairs (i, n-1-i) have same sum. If yes: answer = sum of product of each pair.

Common Pitfalls

  • •All pairs must have same sum. If any pair differs: return -1.
2491.cs
C#
// Approach: Sort; pair smallest with largest; all pairs must sum to same target skill.
// Time: O(n log n) Space: O(1)

public class Solution
{
    public long DividePlayers(int[] skill)
    {
        int n = skill.Length;
        int teamSkill = skill.Sum() / (n / 2);
        long ans = 0;
        Dictionary<int, int> count = new Dictionary<int, int>();

        foreach (int s in skill)
        {
            if (count.ContainsKey(s))
                count[s]++;
            else
                count[s] = 1;
        }

        foreach (var entry in count)
        {
            int s = entry.Key;
            int freq = entry.Value;
            int requiredSkill = teamSkill - s;
            if (!count.ContainsKey(requiredSkill) || count[requiredSkill] != freq)
                return -1;

            ans += (long)s * requiredSkill * freq;
        }

        return ans / 2;
    }
}
Was this solution helpful?

Related Problems