Maximum Performance of a Team - Leetcode 1383 - Python
Vložit
- čas přidán 23. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/maximum...
0:00 - Read the problem
1:57 - Drawing Explanation
11:10 - Coding Explanation
leetcode 1383
#coding #interview #python - Věda a technologie
🚀 neetcode.io/ - 25% OFF LAUNCH SALE
Thanks!
1000rs ? god damn boy
I've got my Amazon final interview next Friday and I just wanted to let you know that I wouldn't have made it nearly as far without you. Thank you for all your videos! You have no idea how many lives you're changing
I think it would be great if you could just show us the code for the brute force way also and then go in depth to explain the optimal solution like you usually do. I personally struggle to sometimes code up even the brute force solution so learning how to do that is something I would value a lot.
Writing a Brute force for this is also not easy. You'll have to make a graph that will give all the possible combination. Then you'll filter combination that has k number of enginees. There will be a function that will calculate the the result and you'll loop through all the feasible combinations
I agree. Even if you don't type it out entirely, you could just show the code and walk through it briefly!
@kaskp to...learn how to do leetcode?
Good suggestion, I'll try to do that in the future. For this problem it doesn't make sense, because even the brute force solution isn't trivial to code and it's mostly unrelated to the optimal solution.
@@NeetCode Do you think being able to solve this problem helped you in interviews? Just curious where to draw the line between actually practical leetcode questions vs great brain teaser but rarely shows up in interviews
To think I once hated dsa coding, have come a long way loving it now, all thanks to you ❤.
I can easily code just after half the video , he explains really good
I also used heap, got to keep the daily streak going!
Thanks for the explanation!
Fan of your amazing videos! Please keep adding more and more
Thank you, this is such a subtle explanation, loved it.
Amazing! Elegant use of the Heap! 🙂
This guy can make hard question to easy, keep it up.
You deserve 1 Mil Subscribers! 🤙
Great explanation, thanks!
2 minutes into the explanation I got the idea, thanks for the video!
Beautiful explanation !!✨
although i use C++, this is very well explained!!
Great. Part of neetcode community. :)
The explanation was great, but I do have a question, is it not better to pop the minimum speed from the heap only if the current speed is greater than that minimum speed?
yeah just realized, if current speed is equal or lower than that minimum speed, because the efficiency will always be lower (already sorted descending), the person should be skipped entirely, like the (3,3) person in the example
I rethought, I guess the reason to update on each entry is to account for the fact that we need to account for all the entries until we have K entries in the heap. So instead of over complicating we can consume all the entries as they show up.
We are popping the item bcz, we need at most k engineers , and for the current engineer being processed , we need k-1 engineers visited so far whose speed is the largest among all of the other engineers previously been processed. I think this helps...
excellent explanation!
awesome video :) helped me alot
Oh spot...super clean explanation!!
amazing explanation, thank u
love from india !!!
amazing explanation !!!!
we are popping when len(heap)==k in heap
and adding curr value in heap..what if the current value is smaller than what we had popped?
very well explained
Amazing!
Isn't size of The Decision Tree be greater than 2^n ?? , as 2^n would be the maximum number of nodes present itself on last level ?
(Just asking for sake of my understanding regarding that Exponential Complexity, else I understand the approach totally )
Lets say if we sort the array in increasing order of their efficiency then we need two nested for loops right? Correct me if my understanding is wrong
Thanks for another great video! I have a question about line 11 and 12, At 14:10, when we pop the minimum value from the heap, shouldn't we first check if this minimum speed is less than the current speed i.e. spd? e.g let's say our K=1 and sorted array is like this [[10, 10], [10, 5], [10, 0]], then we should simply keep the first element as we go through the array without popping the heap.
Okay, I think I understand why that's not a problem. Let's say we remove a speed from the heap and replace it with a spd that is even smaller, now first at line 15 we don't update the res because the last value is still max. More so, let's say later we get another spd' that has a higher value than the last spd, now if this spd' is also larger than the speed which was incorrectly removed, it'll still properly lead to a higher res.
I think you need to read the question again. If you are considering the efficiency at ith index. You must include the speed of it. No matter even if the he popped element has greater speed than current speed.
can you do yesterdays daily? I'm so confused trying to track the dp array. Or buy and sell stock 3 is good too
Thank you
awesome video.. but its more of python stuff this time.. thinking of how to do it in java.
I copied and pasted a lot of stuff and stitched together this code, but I have no idea how it works lol. I knew this could be done with bit manipulation but this method is not any better than the binary search solution, but I still wanted to try it. However, I have no idea how this works except for the msb calculation, which i modified to include (the original did not work).
import math
class Solution:
def mySqrt(self, x: int) -> int:
msb = len(str(bin(x)))
a = 1 = 1
return result
hello, your videos are so impressive, could you just upload the leetcode 526, beautiful arrangement? I really appreciate it.
amazing.
Shouldn't it be 'second *largest* value' instead of 'second smallest value' at 4:48?
I had to watch the video until I saw: sort and which heap to use, after that I was able to solve the problem myself, but it took me 2 hrs, I am gonna cry :D
Same question. 2542. Maximum Subsequence Score
why can't I sort by speed and then maintain a pq by efficiency? at any instant in time the lowest efficiency would be at the top of pq
AMAZING
Is a 0-1 Knapsack solution not possible for this? I was trying to achieve that, but was getting Wrong answer on submit.
How are you gonna store the dp array? it will be a 4d array I guess with large values, will give MLE imo
I think you should teach python for dsa
how to think of this question?
Can you do Leet Code 443 String Compression?
Hi NeetCode, can you help with 2407. Longest Increasing Subsequence II in the contest this morning? Thanks a lot!
I have been trying to find you on google internal, but can not find you haha. Please give me a clue
😛
If u get time can you please make and upload the solution for latest weekly contest last ques(2407. Longest Increasing Subsequence II).
Thanks in advance 😇
hint: use segment trees
@@Abhinavneelam didn't study segment trees yet.
can someone provide java solution ?
pleeease use snake_case in python ;(
Didn't understand the problem statement at all. Ty for explaining in a simple manner. Also for better readability
eng= [[e,s] for e,s in zip(efficiency,speed)]
one liner: engineers = sorted(zip(efficiency, speed), reverse=True)
Reducing number of lines of code doesn’t matter, readability and efficiency matters
@@shreehari2589 Yes it does especially when you are using builtin python methods because they are implemented in C. If you dont believe me try benchmarking sum(range(n)) against a simple for loop.
Wow your so smart dude!! !!1!! Want a trophy?
@@fatropolis6909 no thanks, i already got one from your Mom last night while I taught her my “python” one-liners 😉
@@shreehari2589 This is readable for any python developers and is definitely efficient
can someone help in my java code? Some test cases are not getting passed.Thank you.
class Solution {
public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
int[][] zip = new int[speed.length][2]; //eff,speed
for(int i = 0; i < speed.length; i++){
zip[i] = new int[] {efficiency[i], speed[i]};
}
Arrays.sort(zip, (a,b) -> Integer.compare(b[0], a[0]));
Queue minHeap = new PriorityQueue((a,b) -> Integer.compare(a,b));
int res = 0;
int totalSpeed = 0;
for(int[] pair : zip){
if(minHeap.size() == k){
totalSpeed -= minHeap.poll();
}
int eff = pair[0], spd = pair[1];
minHeap.add(spd);
totalSpeed += spd;
res = Math.max(res, totalSpeed*eff);
}
return (int)(res % (Math.pow(10,9) + 7));
}
}
Thanks for the intution, I solved this using 2 Priority queues
int maxPerformance(int n, vector& speed, vector& eff, int k) {
int mod=1e9+7;
priority_queue pq;
for(int i=0;ik){
sum-=minheap.top();
minheap.pop();
}
res=max(res,pq.top().first*sum);
pq.pop();
}
return res%mod;
}