Awesome video as always man. Thanks so much for making these! Two suggestions: 1. Once you have solved the question, go through time and space complexity analysis as if an interviewer asked you about it. This helps a lot for the solutions where it isn't that clear. 2. When discussing your answer before coding, try to talk about alternatives because usually in interviews, it's not a one shot situation. Example: for this solution, why did you choose to go with a maxheap instead of creating tuples and sorting the list? (maybe choose two solutions where one is clearly less optimal though) I think that these are the only thing missing from these videos: more discussion about the solution because you definitely have the solution itself down solid! Still, great work, keep it up!
Thank you for sharing this video, as of now I am preparing for companies like Google, Microsoft and Amazon I strongly believe that by following your channel I will get to understand the interview pattern and possible questions that might get asked in these companies.
Thanks so much! If you're preparing for interview especially large companies/FAANG and you like my explanations I strongly recommend signing up for the interviewing service I created: thedailybyte.dev/?ref=kevin I'd join the annual tier if you can :)
I just did it using PriorityQueue with [values,label], but I think creating classes gives you an edge in interviews as you get to show your OOP knowledge, though its a simple class.
isn't adding an item to a max heap done within O(logn) since you need to heapify? doesn't that makes populating the heap O(nlogn)? since you need ot heapify for each item?
First off, great work, I learned a lot from your video. I do have some questions however, when I see this problem I think of dynamic programming, first filter all the unique labeled items into there own sets, then pick the allowed number of items from those sets (from greatest to least) into a bigger list, next find the max subsequence of that bigger list, btw this is not accounting for the fact that this list would now need to be sorted from greatest to least, but we could do a merge sort type of deal to put sorted items into the newly sorted list (our complexity is growing) but I was thinking instead of wasting time by putting the unique labeled items into there own set, if the labels are all grouped initially which it looks like they were then you could simply pick the max of each label, this would first require a sort however so I think, if this would even work, it would still be nLogn damn... anyways great video thanks!
you could also have made the label member an index into an array of label counts instead of using a hashmap. It would probably work better in C++ where you can grow a vector: you wouldn't know the size of the array before allocating it. Minor optimization, maybe. Good work as always (I solved it the same way but it took a while to figure out what the problem was asking! Thank goodness for LC examples)
hmmm: there's no guarantee that the labels increase monotonically, nor relate to anything: you could have 10,000 numbers with label 1 and 10,000 with label 20,000. The hashmap solution is better
Thank you so much Kevin 🙂. I was able to think and solve before seing your solution. Believe me it turned with exact data structures you coded 😀. You are a true gem. Please keep helping us. Thanks a ton.
Building a heap is O(N). Inserting one element in heap of N elements is O(logN) but while building the size of heap is varying from 0 to N so O(NLogN) is a loose bound, O(N) is much tighter. CLRS has more formal proof if you're interested, or any other source that you can Google
Hey Kevin. This is possible in O(n) time because the values are bounded. Basic idea is to map the values to an array which has 2001 (max num is 2000) empty elements, and keep track of a list of labels per value, then iterate from the end of this array and keep track of the label uses and pick the numbers you want. I posted the solution on leetcode discussion if anyone is interested. leetcode.com/problems/largest-values-from-labels/discuss/670367/Python3-O(n)-Solution
Honest question, for your videos do you prepare your answers ahead of time or do you look at the problem and solve it in real time? Either way great content, subscribing!
Can you have a hash map of label keys, where each value object will have a min heap of size k = "max count by label" - to store max values with the label. Wouldn't the time complexity be n log(k) this way?
Pratik Chowdhury start with the easiest of problems and build from there! These questions are hard so don’t beat yourself up just keep practicing you can do it!!!
@@KevinNaughtonJr Thanks for reply. My intuition is backtracking. It's not easy to come out the greedy solution. One of my teacher taught there is less and less greedy problems. I should keep my mind open, bigger. ^_^
c# public class Solution { public int LargestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) { //Sort the arrays using values as keys and labels as values. Array.Sort(values,labels);
//use dictionary to store key as label[i] value as useLimit max value. Dictionary usedLabels=new Dictionary();
smash like and leave a comment to help ~the algorithm~
instagram: instagram.com/kevinnaughtonjr
twitter: twitter.com/kevinnaughtonjr
Awesome video as always man. Thanks so much for making these!
Two suggestions:
1. Once you have solved the question, go through time and space complexity analysis as if an interviewer asked you about it. This helps a lot for the solutions where it isn't that clear.
2. When discussing your answer before coding, try to talk about alternatives because usually in interviews, it's not a one shot situation. Example: for this solution, why did you choose to go with a maxheap instead of creating tuples and sorting the list? (maybe choose two solutions where one is clearly less optimal though)
I think that these are the only thing missing from these videos: more discussion about the solution because you definitely have the solution itself down solid! Still, great work, keep it up!
Thank you for sharing this video, as of now I am preparing for companies like Google, Microsoft and Amazon I strongly believe that by following your channel I will get to understand the interview pattern and possible questions that might get asked in these companies.
Thanks so much! If you're preparing for interview especially large companies/FAANG and you like my explanations I strongly recommend signing up for the interviewing service I created: thedailybyte.dev/?ref=kevin I'd join the annual tier if you can :)
I just did it using PriorityQueue with [values,label], but I think creating classes gives you an edge in interviews as you get to show your OOP knowledge, though its a simple class.
Thanks for the content. You and Nick White are my gurus.
anytime and yeah Nick is dope
Just in time for my Google phone interview :)
woooo happy to hear that :)
Keep On Coding your channel is also amazing, I've watched almost all of your videos!
@@farhan787 😁😁
@@KeepOnCoding How was it?
Thanks! Like the way you do not populate the map in a separate loop before iterating thru the heap elements.
thanks!
you could add them all to the heap in the first iteration. i don't think there was a point in making the arraylist and doing the .addAll call.
What is the necessity of making an ArrayList? can't we just add to the heap items within the loop you used to populate the ArrayList?
Thank you so much fr these valuable videos. Really appreciate your work man. Keep going.
anytime Ankit thank YOU for supporting my channel!
isn't adding an item to a max heap done within O(logn) since you need to heapify? doesn't that makes populating the heap O(nlogn)? since you need ot heapify for each item?
Building a Heap actually takes just O(n). Just google and you'll find plenty of resources explaining the proof for complexity.
First off, great work, I learned a lot from your video. I do have some questions however, when I see this problem I think of dynamic programming, first filter all the unique labeled items into there own sets, then pick the allowed number of items from those sets (from greatest to least) into a bigger list, next find the max subsequence of that bigger list, btw this is not accounting for the fact that this list would now need to be sorted from greatest to least, but we could do a merge sort type of deal to put sorted items into the newly sorted list (our complexity is growing) but I was thinking instead of wasting time by putting the unique labeled items into there own set, if the labels are all grouped initially which it looks like they were then you could simply pick the max of each label, this would first require a sort however so I think, if this would even work, it would still be nLogn damn... anyways great video thanks!
Thanks a ton!
anytime!
I think Map isnt needed as one could track the usage count of currentLabel usage using just one var, and then reset the var when switching labels
you could also have made the label member an index into an array of label counts instead of using a hashmap. It would probably work better in C++ where you can grow a vector: you wouldn't know the size of the array before allocating it. Minor optimization, maybe. Good work as always (I solved it the same way but it took a while to figure out what the problem was asking! Thank goodness for LC examples)
hmmm: there's no guarantee that the labels increase monotonically, nor relate to anything: you could have 10,000 numbers with label 1 and 10,000 with label 20,000. The hashmap solution is better
interesting!
@@treyquattro ahhh ok gotcha
what mic do you use?
Thanks Kevin :) I had tough time to understand this question... You made it easy \m/
Pratik Dekate thanks Pratik happy to hear that :)
Is it Okay to Java as a sword in CP or Interview personally I love Java, but I have heard that if we use C++ then we safe form any perceptive.
i personally find python the fastest way to code up solutions. super concise and readable
Best video series I have seen
thanks Charlie appreciate that
Thank you so much Kevin 🙂. I was able to think and solve before seing your solution. Believe me it turned with exact data structures you coded 😀. You are a true gem. Please keep helping us. Thanks a ton.
Mohammed Nadeem anytime Mohammed thanks so much for supporting my channel!
Won't adding all the elements to the heap be O(NLogN)? I think I heard O(N) during the explanation. Binary heap is O(logN) insert and delete
Building a heap is O(N). Inserting one element in heap of N elements is O(logN) but while building the size of heap is varying from 0 to N so O(NLogN) is a loose bound, O(N) is much tighter. CLRS has more formal proof if you're interested, or any other source that you can Google
Awesome video Kevin, can you please make a video on "970.Powerful Integers", with an optimal solution...
i'll put it on my list!
just love your content dude
Can you please do a video on "347. Top K Frequent Elements
"?
Hey Kevin. This is possible in O(n) time because the values are bounded. Basic idea is to map the values to an array which has 2001 (max num is 2000) empty elements, and keep track of a list of labels per value, then iterate from the end of this array and keep track of the label uses and pick the numbers you want. I posted the solution on leetcode discussion if anyone is interested. leetcode.com/problems/largest-values-from-labels/discuss/670367/Python3-O(n)-Solution
Honest question, for your videos do you prepare your answers ahead of time or do you look at the problem and solve it in real time? Either way great content, subscribing!
thanks! And normally I make sure I understand the problem enough to be able to explain it, meaning I've solved the problem previously
Your videos are awesome!
Kenan Li thanks Kenan!!!
Can you have a hash map of label keys, where each value object will have a min heap of size k = "max count by label" - to store max values with the label. Wouldn't the time complexity be n log(k) this way?
Dmitry Karpenko I think if we want nlogk we can prob just adjust my solution to ensure our heap size is at most k when inserting elements
@@KevinNaughtonJr If you're going group by group, that sounds possible.
I don't have a solution myself yet, so thanks anyway!
Dmitry Karpenko anytime!
Really helpful video and I never miss your video
thanks Deependra I appreciate the support! :)
I would recommend once you finish the answer, try to optimize it and suggest how we can imrove the solution.
jatin gupta thanks for the suggestion!
It might be sub-optimal, but I just sorted the values and chose the best values from there instead of a heap
it's the same thing. O( N log N )
i feel miserable and depressed everytime i try to solve a problem and fail, which is most of the time :(
Pratik Chowdhury start with the easiest of problems and build from there! These questions are hard so don’t beat yourself up just keep practicing you can do it!!!
It took me 10 minutes to understand purpose of use_limit, then took me 1 hour to complete the code.
I went with DFS first. ^_^
as long as you got it done! :)
@@KevinNaughtonJr go to sleep dude it's late
@@jak0495 it's waaay past my bedtime J
@@KevinNaughtonJr Thanks for reply. My intuition is backtracking.
It's not easy to come out the greedy solution. One of my teacher taught there is less and less greedy problems.
I should keep my mind open, bigger. ^_^
How many leetcode problems did you solve so far?
Amazon Oops plz
Manish Tiwari which problem is that?
@@KevinNaughtonJr amazon asks questions related to Oops like black jack implementation
Manish Tiwari ahhh I see
c#
public class Solution {
public int LargestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
//Sort the arrays using values as keys and labels as values.
Array.Sort(values,labels);
//use dictionary to store key as label[i] value as useLimit max value.
Dictionary usedLabels=new Dictionary();
int maxSum=0;
//loop values from ending to start
for(int i=values.Length-1;i>=0&&numWanted>0;i--)
{
if(!usedLabels.ContainsKey(labels[i]))
{
usedLabels.Add(labels[i],useLimit);
}
if(usedLabels[labels[i]]>0)
{
maxSum+=values[i];
usedLabels[labels[i]]--;
numWanted--;
}
}
return maxSum;
}
}
the List was necessary you could just do maxHeap.add(new Item(values[i], labels[i])); ...btw good video