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)
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.
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; } }
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.
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
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
It’s just a habit to watch your videos, even though I solved the problem easily.
Naah u just come to make fun of that one struggling beginner dude
@@zweitekonto9654he came here to make fun on me
7:52 It's because this edge case would never arise since the count of elements is even.
bingo
I did it exactly like you did and was surprised to see so many solutions with sorting
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)
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.
amazing explanation, thank you!
Why we are doing 2* total % Len (skill), can't we just do total % Len (skill)? same for the target?
Bro I just had this question in an interview this week
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;
}
}
solved it with sort
i dont understand the last bit about diff and s being same, why should we move the decrementing condition above?
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.
Solved it!
I did it the same way as you, but it is slower than the other solutions
even though I solved it, I had to watch the vid.
First
My O(n) solution beats 40% whereas O(nlogn) beats 87%....
Leetcode.....😅😅😅😅
It's not uncommon for hash table to be pretty slow. It has a trash O(1).
well, let's be honest, if your O(n) solution is slower, then is not Leetcode fault.. is a layer 8 issue...
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
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
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
great
first