Divide Players Into Teams of Equal Skill - Leetcode 2491 - Python

[@Kokurorokuko]

I did it exactly like you did and was surprised to see so many solutions with sorting

[@s0lomate]

It’s just a habit to watch your videos, even though I solved the problem easily.

[@zweitekonto9654]

Naah u just come to make fun of that one struggling beginner dude

[@dontignore5567]

@@zweitekonto9654he came here to make fun on me

[@rjarora]

7:52 It's because this edge case would never arise since the count of elements is even.

[@rohitkumaram]

bingo

[@aitormonrealurcelay3500]

As always, thank you for your daily solutions!

[@Drakula1996]

Beginner here... is this a good solution? if len(skill) % 2: return -1 skill.sort() maxChem = sum(skill) // (len(skill) // 2) l, r = 0, len(skill) - 1 res = [] while l < r: if skill[l] + skill[r] == maxChem: res.append(skill[l] * skill[r]) else: return -1 l += 1 r -= 1 return sum(res)

[@leeroymlg4692]

I like the way you're thinking, but it's a O(nlogn) solution which is worse than O(n). This is because you are sorting the input. But it's a good nlogn solution, just could be more time efficient.

[@PerseRos285]

amazing explanation, thank you!

[@praveenkumarv2727]

Answer in Java class Solution { public long dividePlayers(int[] skill) { if(skill.length==2){ return skill[0]*skill[1]; } Arrays.sort(skill); long sum = 0; int n = skill.length; int targetSum = skill[0] + skill[n - 1]; for (int i = 0, j = n - 1; i < j; i++, j--) { if (skill[i] + skill[j] != targetSum) { return -1; } sum += (long) skill[i] * skill[j]; } return sum; } }

[@satyamjha68]

Solved it!

[@eternal8lueforever]

Bro I just had this question in an interview this week

[@sabukuna]

solved it with sort

[@romi._.]

Why we are doing 2* total % Len (skill), can't we just do total % Len (skill)? same for the target?

[@eliteturtle6090]

I did it the same way as you, but it is slower than the other solutions

[@awalkingnosebleed]

i dont understand the last bit about diff and s being same, why should we move the decrementing condition above?

[@salami6721]

The thought process is that we already looked at s, and if s and diff are the same then we're looking at the same element twice. So, the solution is to decrement s so that we can track we already checked it once. But because we checked for the array to be even, I don't think this edge case will happen anyways.

[@faaeizkhan6134]

even though I solved it, I had to watch the vid.

[@shikharupadhyay7435]

My O(n) solution beats 40% whereas O(nlogn) beats 87%.... Leetcode.....😅😅😅😅

[@reeree519]

It's not uncommon for hash table to be pretty slow. It has a trash O(1).

[@tucho6]

well, let's be honest, if your O(n) solution is slower, then is not Leetcode fault.. is a layer 8 issue...

[@maazfaisal1649]

first

[@pruthvinarayana9568]

as we are any way traversing the whole array , we can skip the 1st If statement in side the loop, and decrement the another value of the pair afterwards , any way it doesn't change anything 😺 class Solution: def dividePlayers(self, skill: List[int]) -> int: myhash = {} for n in skill: if n in myhash: myhash[n] += 1 else: myhash[n] = 1 target = sum(skill) // (len(skill) // 2) ans = 0 for n in skill: if (target - n in myhash) and (myhash[target - n] > 0) : myhash[target - n] -= 1 ans += n * (target - n) else: return -1 return ans // 2

[@tucho6]

you can do the last for from 0 to target and then directly do: ans += myhash[i]i*(target-i); you'll go from O(N) to O(target) in that part

[@adoreyourpain]

Quick tip for this part; for n in skill: if n in myhash: myhash[n] += 1 else: myhash[n] = 1 You could instead write for n in skill: myhash[n] = 1 + myhash.get(n, 0) Just to make it even cleaner, that way you don't need to check if it is in there before hand because it'll just return 1+0, otherwise 1 + whatever it's value already is

[@TheFactualKai]

great

[@tylera3126]

First