Largest Values from Labels

Поделиться
HTML-код
  • Опубликовано: 9 ноя 2024

Комментарии • 74

  • @KevinNaughtonJr
    @KevinNaughtonJr  4 года назад +7

    smash like and leave a comment to help ~the algorithm~
    instagram: instagram.com/kevinnaughtonjr
    twitter: twitter.com/kevinnaughtonjr

  • @bdc225
    @bdc225 4 года назад +9

    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!

  • @diineshkanojia8923
    @diineshkanojia8923 4 года назад +1

    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.

    • @KevinNaughtonJr
      @KevinNaughtonJr  4 года назад

      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 :)

  • @utsavshrestha7162
    @utsavshrestha7162 2 года назад

    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.

  • @anoopm3605
    @anoopm3605 4 года назад +2

    Thanks for the content. You and Nick White are my gurus.

  • @KeepOnCoding
    @KeepOnCoding 4 года назад +5

    Just in time for my Google phone interview :)

    • @KevinNaughtonJr
      @KevinNaughtonJr  4 года назад

      woooo happy to hear that :)

    • @farhan787
      @farhan787 4 года назад +1

      Keep On Coding your channel is also amazing, I've watched almost all of your videos!

    • @KeepOnCoding
      @KeepOnCoding 4 года назад

      @@farhan787 😁😁

    • @kadjojc
      @kadjojc 4 года назад

      @@KeepOnCoding How was it?

  • @0anant0
    @0anant0 4 года назад

    Thanks! Like the way you do not populate the map in a separate loop before iterating thru the heap elements.

    • @KevinNaughtonJr
      @KevinNaughtonJr  4 года назад

      thanks!

    • @JM_utube
      @JM_utube 4 года назад

      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.

  • @yugioh8810
    @yugioh8810 4 года назад +1

    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?

  • @casual_chess
    @casual_chess 4 года назад +2

    Thank you so much fr these valuable videos. Really appreciate your work man. Keep going.

    • @KevinNaughtonJr
      @KevinNaughtonJr  4 года назад

      anytime Ankit thank YOU for supporting my channel!

  • @yugioh8810
    @yugioh8810 4 года назад +1

    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?

    • @popstaravex
      @popstaravex 4 года назад +1

      Building a Heap actually takes just O(n). Just google and you'll find plenty of resources explaining the proof for complexity.

  • @tman7022
    @tman7022 4 года назад

    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!

  • @Nehamore1909
    @Nehamore1909 4 года назад +1

    Thanks a ton!

  • @kumarc4853
    @kumarc4853 3 года назад

    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

  • @treyquattro
    @treyquattro 4 года назад

    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)

    • @treyquattro
      @treyquattro 4 года назад

      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

    • @KevinNaughtonJr
      @KevinNaughtonJr  4 года назад

      interesting!

    • @KevinNaughtonJr
      @KevinNaughtonJr  4 года назад

      @@treyquattro ahhh ok gotcha

  • @gulshansingh3933
    @gulshansingh3933 3 года назад

    what mic do you use?

  • @reallifegambits
    @reallifegambits 4 года назад +1

    Thanks Kevin :) I had tough time to understand this question... You made it easy \m/

    • @KevinNaughtonJr
      @KevinNaughtonJr  4 года назад

      Pratik Dekate thanks Pratik happy to hear that :)

  • @dipakraut6058
    @dipakraut6058 4 года назад +2

    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.

    • @kumarc4853
      @kumarc4853 3 года назад +1

      i personally find python the fastest way to code up solutions. super concise and readable

  • @RottenWoodInPower
    @RottenWoodInPower 4 года назад

    Best video series I have seen

  • @mohammednadeem333
    @mohammednadeem333 4 года назад

    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.

    • @KevinNaughtonJr
      @KevinNaughtonJr  4 года назад +1

      Mohammed Nadeem anytime Mohammed thanks so much for supporting my channel!

  • @Smcool123456
    @Smcool123456 3 года назад

    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

    • @rahulsangvikar7973
      @rahulsangvikar7973 2 года назад +1

      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

  • @deepakwalia8898
    @deepakwalia8898 4 года назад

    Awesome video Kevin, can you please make a video on "970.Powerful Integers", with an optimal solution...

  • @beardman4152
    @beardman4152 3 года назад

    just love your content dude

  • @shubhammittalSHM
    @shubhammittalSHM 4 года назад

    Can you please do a video on "347. Top K Frequent Elements
    "?

  • @scnullois
    @scnullois 4 года назад +1

    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

  • @icyzing1
    @icyzing1 4 года назад

    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!

    • @KevinNaughtonJr
      @KevinNaughtonJr  4 года назад +2

      thanks! And normally I make sure I understand the problem enough to be able to explain it, meaning I've solved the problem previously

  • @kenanli5867
    @kenanli5867 4 года назад +1

    Your videos are awesome!

  • @dmitrykarpenko2271
    @dmitrykarpenko2271 4 года назад

    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?

    • @KevinNaughtonJr
      @KevinNaughtonJr  4 года назад

      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

    • @dmitrykarpenko2271
      @dmitrykarpenko2271 4 года назад

      @@KevinNaughtonJr If you're going group by group, that sounds possible.
      I don't have a solution myself yet, so thanks anyway!

    • @KevinNaughtonJr
      @KevinNaughtonJr  4 года назад

      Dmitry Karpenko anytime!

  • @deependramnit
    @deependramnit 4 года назад

    Really helpful video and I never miss your video

    • @KevinNaughtonJr
      @KevinNaughtonJr  4 года назад

      thanks Deependra I appreciate the support! :)

  • @jatingupta5986
    @jatingupta5986 4 года назад

    I would recommend once you finish the answer, try to optimize it and suggest how we can imrove the solution.

  • @adedayoologunde3055
    @adedayoologunde3055 4 года назад

    It might be sub-optimal, but I just sorted the values and chose the best values from there instead of a heap

    • @gaureesha9840
      @gaureesha9840 4 года назад

      it's the same thing. O( N log N )

  • @pratikchowdhury9210
    @pratikchowdhury9210 4 года назад

    i feel miserable and depressed everytime i try to solve a problem and fail, which is most of the time :(

    • @KevinNaughtonJr
      @KevinNaughtonJr  4 года назад +2

      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!!!

  • @goodwish1543
    @goodwish1543 4 года назад

    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. ^_^

    • @KevinNaughtonJr
      @KevinNaughtonJr  4 года назад

      as long as you got it done! :)

    • @jak0495
      @jak0495 4 года назад

      @@KevinNaughtonJr go to sleep dude it's late

    • @KevinNaughtonJr
      @KevinNaughtonJr  4 года назад

      @@jak0495 it's waaay past my bedtime J

    • @goodwish1543
      @goodwish1543 4 года назад

      @@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. ^_^

  • @kadjojc
    @kadjojc 4 года назад

    How many leetcode problems did you solve so far?

  • @ManishTiwari-or8zt
    @ManishTiwari-or8zt 4 года назад

    Amazon Oops plz

    • @KevinNaughtonJr
      @KevinNaughtonJr  4 года назад

      Manish Tiwari which problem is that?

    • @ManishTiwari-or8zt
      @ManishTiwari-or8zt 4 года назад

      @@KevinNaughtonJr amazon asks questions related to Oops like black jack implementation

    • @KevinNaughtonJr
      @KevinNaughtonJr  4 года назад +1

      Manish Tiwari ahhh I see

  • @techtea5911
    @techtea5911 3 года назад

    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;
    }
    }

  • @Mike-ci5io
    @Mike-ci5io Год назад

    the List was necessary you could just do maxHeap.add(new Item(values[i], labels[i])); ...btw good video