Problem of The Day: Divide Players Into Teams of Equal Skill

2 min read 545 words

Problem Statement

leetcode problem link

Solution [accepted]

class Solution:
    def dividePlayers(self, skill: List[int]) -> int:
        skill.sort()
        l, r = 0, len(skill) - 1
        res = 0
        prev_sum = None
        while l < r:
            curr_sum = skill[l] + skill[r]
            if prev_sum is not None and curr_sum != prev_sum:
                return -1
            prev_sum = curr_sum
            res += (skill[l] * skill[r])
            l += 1
            r -= 1
        return res

public class Solution {
    public long DividePlayers(int[] skill) {
        Array.Sort(skill);
        int left = 0;
        int right = skill.Length - 1;
        long res = 0;
        var prevSum = long.MinValue;
        while (left < right) {
            var currSum = skill[left] + skill[right];
            if (prevSum != long.MinValue && prevSum != currSum) {
                return -1;
            }
            prevSum = currSum;
            res += (skill[left] * skill[right]);
            left += 1;
            right -= 1;
        }
        return res;
    }
}

• time: O(nlogn)
• space: O(1)

Editorial

Approach 1: Sorting

class Solution:
    def dividePlayers(self, skill: List[int]) -> int:
        skill.sort()
        n = len(skill)
        total_chemistry = 0

        # Calculate the target sum
        target_team_skill = skill[0] + skill[-1]

        # Iterate through half of the array, pairing players from both ends
        for i in range(n // 2):
            # If any team's skill doesn't match the target, return -1
            if skill[i] + skill[-i - 1] != target_team_skill:
                return -1

            # Calculate and add the chemistry of the current team
            total_chemistry += skill[i] * skill[-i - 1]

        return total_chemistry