The Number of Beautiful Subsets - Leetcode 2597 - Python

Поділитися
Вставка
  • Опубліковано 16 гру 2024

КОМЕНТАРІ • 82

  • @NeetCodeIO
    @NeetCodeIO  6 місяців тому +72

    I'm curious how much you guys care about seeing the most optimal solution? I probably could've gotten this video out a few hours earlier if I just showed the first solution.

    • @sauravsingh4497
      @sauravsingh4497 6 місяців тому +49

      I personally watch your videos even after solving the problem because I know you will come up with the most optimal solution.
      So I want the most optimal solution.

    • @levylost8550
      @levylost8550 6 місяців тому +14

      I love optimal solutions, it introduces new and clever way of thinking and in my opinion is what improves problem solving skills and get us out of comfort zone. You are doing great work!

    • @grantpeterson2524
      @grantpeterson2524 6 місяців тому +9

      Definitely prefer having the optimal solution, at the end of the day the daily challenges are temporary but the content is useful indefinitely, soI think it's better to take longer but give people the assurance that a solution is optimal or near-optimal

    • @kahafb
      @kahafb 6 місяців тому +5

      I like seeing both simple and optimal solutions!

    • @kevinwang8632
      @kevinwang8632 6 місяців тому +4

      I care more about practicing common patterns that I'll see in interviews than crackhead solutions, which I feel like this one leans towards. Just personal opinion though

  • @chien-yuyeh9386
    @chien-yuyeh9386 6 місяців тому +18

    For me, I enjoy the way you’re thinking and analyzing for solving these problems.
    I’m trying to learn how to solve a problem like you.
    So, no matter it’s optimal solution or not, it’s fine to me.
    But actually, hope the solution to that question is enough to the interview because I’m preparing for this now.😂

  • @MP-ny3ep
    @MP-ny3ep 6 місяців тому +3

    The optimal solution was crazy. Kudos for explaining it so well.

  • @Pegasus02Kr
    @Pegasus02Kr 6 місяців тому +2

    I always love your way of explaining optimal solutions. Even though some of those are so difficult to follow or cannot be applied to other problems, I enjoy watching your intuition or logics in thought process.
    The only solutions I didn't care so far were solving tree traversal in iterative way, which are more complicated while being neither optimal nor practical

  • @jagrutitiwari2551
    @jagrutitiwari2551 6 місяців тому +4

    As a beginner, I care about a solution. Most importantly understand that solution through a dry run.
    Optimization is not my priority as of now.

  • @jotrades26
    @jotrades26 6 місяців тому

    Bro, I had the first step where we try to select the numbers which don't conflict, but the neat part comes into picture when you pick the numbers which do conflict, afterwards its boiling down to house robber and a beautiful way to solve using basic set theory, I am mind blown !!!

  • @aximilian15
    @aximilian15 6 місяців тому

    Even though I code in Java and usually skip your Python code, I still check out your explanations of how to solve the problems and your thinking process, because you are just damn good at it.

  • @carrotiq6879
    @carrotiq6879 6 місяців тому +8

    how did u come up with this solution, like what is your thinking process. pls do make a video about that. And yes i care about the optimal solution.

  • @OrphanedZombie
    @OrphanedZombie 6 місяців тому

    I was able to use the suboptimal approach with just a hashset, as long as I sorted the input array beforehand.

  • @sourvad
    @sourvad 6 місяців тому

    You are the hero we don't deserve, but we all need

  • @shivkrishnajaiswal8394
    @shivkrishnajaiswal8394 6 місяців тому

    @NeetCodeIO instead of defaultdict(int), you can use Counter class from collections

  • @pastori2672
    @pastori2672 6 місяців тому

    great explanation man i actually understood the optimal solution this time

  • @nikhil199029
    @nikhil199029 6 місяців тому

    One suggestion, use the statistics formula to simplify the formula.
    Number of ways in which we can k elements from N elements such that one or more of other elements is not present-> use this as base case

  • @rjarora
    @rjarora 6 місяців тому

    Not sure about the subsets, but your explanation is definitely beautiful!

  • @brokecoder
    @brokecoder 6 місяців тому

    feels good, being able to solve this without neetcode, (for once)! (thanks neet)
    ```
    from collections import defaultdict
    class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int:
    res = []
    currPath = []
    counter = defaultdict(int)
    def dfs(i):
    if i >= len(nums):
    if currPath:
    res.append(currPath.copy())
    return
    lowerBound = nums[i] - k
    upperBound = nums[i] + k
    if counter[lowerBound] == 0 and counter[upperBound] == 0:
    currPath.append(nums[i])
    counter[nums[i]] += 1
    dfs(i+1)
    currPath.pop()
    counter[nums[i]] -= 1
    dfs(i+1)
    dfs(0)
    return len(res)
    ```

  • @ap2s2000
    @ap2s2000 6 місяців тому +2

    3:20 - Isn't the calculation for the amount of subarrays N*(N+1)/2, not N^2?

    • @NeetCodeIO
      @NeetCodeIO  6 місяців тому +1

      yeah i was thinking along the lines of the Big O complexity

    • @ap2s2000
      @ap2s2000 6 місяців тому

      @@NeetCodeIO Got it, thanks

  • @sahilhedau7377
    @sahilhedau7377 6 місяців тому +1

    For creating the groups, can we just make the groups according to number's remainder when they are divided by k. So we have k groups initialized for each remainder from 0 to k-1, and we will iterate through all the numbers in array then if num%k == 2 then we will add that num in 2nd index group. Like, group[num%k].push_back(num).

  • @prasunroy2802
    @prasunroy2802 6 місяців тому

    Thank you

  • @ChiragMalaviya-so7tw
    @ChiragMalaviya-so7tw 6 місяців тому +6

    How do people come up with these solution @NeetCodeIO...

  • @joydeeprony89
    @joydeeprony89 6 місяців тому

    bro back after long time

  • @MadhuSanduri
    @MadhuSanduri 6 місяців тому

    First I'm feeling is my preparation is in good way!!😢
    Because I solved 20+ problems on backtracking myself but can't understand the this problem

  • @DeathSugar
    @DeathSugar 6 місяців тому

    from 2.6 seconds to 60 milliseconds i would say is pretty huge optimisation. literallty x40

  • @irabucc469
    @irabucc469 6 місяців тому

    That's so elegant

  • @rostyslavmochulskyi159
    @rostyslavmochulskyi159 6 місяців тому +1

    Would an optimal solution be required to pass the interview, or will backtracking be enough?

  • @albedo9617
    @albedo9617 6 місяців тому

    This is similar to the question that was asked in codeforces round 945 (I think)

  • @EduarteBDO
    @EduarteBDO 6 місяців тому

    For this question I was stuck in the first answer trying to use a hashset and not knowing why it wasn't working.

  • @varunpalsingh3822
    @varunpalsingh3822 6 місяців тому

    thank you 🙂

  • @IntelliStar_
    @IntelliStar_ 2 місяці тому

    I would never come up with the optimal solution in an interview

  • @donalshijan5615
    @donalshijan5615 5 місяців тому

    Could there be a mistake in complexity analysis here, cause the similar solution on the editorial section of leetcode claims it's time complexity to be nlogn + 2^n in worst case, which makes sense to me since helper function will be called at most 2 times recursively in each call, and in the worst case all n elements of the array can be in the same group making time complexity of the helper function to be 2^n in the worst case.

  • @Perry-tf2pr
    @Perry-tf2pr 6 місяців тому +1

    insane

  • @jaatharsh
    @jaatharsh 6 місяців тому

    we need both simple + optimal

  • @mohaimenchowdhury
    @mohaimenchowdhury 6 місяців тому

    Hey @neetcode, I have a curiosity. I have seen your contests graph in Leetcode, no offence this is much impressive but I have noticed some times you have struggled in some contests. My question is how had you overcome those days, like when I can not perform as expected in the contests or can not come up with solutions for the daily challenges, my subconscious mind lets me to rethink if I should continue grinding leetcode or I should quit. Your profile is a true inspiration because I can see myself as struggling as you but sometimes it's difficult to keep myself motivated.
    I already have a 40hrs/week job and dreaming to crack bigtechs, it's not always easy to be consistently motivated everyday specially when facing some crackhead problems like this and I can not have much time per day for trying hard.

  • @moabd7575
    @moabd7575 6 місяців тому

    brute force is giving TLE with c++
    is it because c++ sucks at recursion or did i do something wrong?
    class Solution {
    public:
    int beautifulSubsets(vector& nums, int k) {
    int n = nums.size();
    function dfs = [&](int i, unordered_map count){
    if(i == n) return 1;
    int res = dfs(i+1, count);
    if(!count[nums[i]-k] && !count[nums[i]+k]){
    count[nums[i]]++;
    res += dfs(i+1, count);
    count[nums[i]]--;
    }
    return res;
    };
    unordered_map map;
    return dfs(0, map) - 1;
    }
    };

    • @moabd7575
      @moabd7575 6 місяців тому +1

      nvm, i passed hash map by reference and it worked

    • @kgCode658
      @kgCode658 6 місяців тому

      @@moabd7575 yes thats why u backtrack coz you dont have to copy hashmap

  • @MohanRam-mq2pk
    @MohanRam-mq2pk 6 місяців тому

    bro try to be consistent

  • @Antinormanisto
    @Antinormanisto 6 місяців тому

    What the magic? I don't know how I could find the first solution even

  • @asifiqbal21
    @asifiqbal21 6 місяців тому +1

    Does anybody expect the optimal solution in an interview?

  • @akash-kumar737
    @akash-kumar737 6 місяців тому +1

    Fuck optimal solution - The problem with optimal solution is that how many will remember the intuitive when we give interview.

  • @anay-208
    @anay-208 6 місяців тому

    You're just not explaining "Why are we doing that, how does that help with our problem?", in detail, for some problems. Rest I'm able to understand

    • @NeetCodeIO
      @NeetCodeIO  6 місяців тому

      Thanks for the feedback. Was there a specific part of the algorithm that you had in mind?

    • @anay-208
      @anay-208 6 місяців тому

      @@NeetCodeIO no, i understood the question well, however, first, with the dfs solution, I wasn’t able to understand, how will that work? By doing a dry run, it helped me understand better. Recommending you to do that.
      I almost see your vids daily, and My another suggestion is that, there are some newbie people who don’t know meaning of XOR/OR, or the Counter function. It would be worth making separate UA-cam video/short relating to it, and link it in the description of the videos using it.
      I’m giving my feedback as a high school student, I’m doing leetcode as it’ll be beneficial for my future

  • @michael._.
    @michael._. 6 місяців тому +1

  • @albedo9617
    @albedo9617 6 місяців тому

    import java.util.HashMap;
    class Solution {
    public int beautifulSubsets(int[] nums, int k) {
    return iterator(nums,k,0,new HashMap());
    }

    public int iterator(int[] nums, int k, int i, HashMap counter){
    if(i == nums.length ){
    return 1;
    }
    int res = 0;

    res += iterator(nums,k,i+1,counter);
    // include
    if(!counter.containsKey(nums[i]-k) && !counter.containsKey(nums[i]+k)){
    counter.put(nums[i],counter.getOrDefault(nums[i],0)+1);
    res += iterator(nums,k,i+1,counter);
    counter.put(nums[i],counter.getOrDefault(nums[i],0)-1);
    }
    return res;
    }
    }
    What am I doing wrong here?

    • @JRK_RIDES
      @JRK_RIDES 6 місяців тому

      You're just checking for whether the key exists or not but you should check if the key doesn't exist OR if it does the frequency or count of nums[i] should be zero.
      Hope it helps. If not I can share my java solution if you want.

    • @albedo9617
      @albedo9617 6 місяців тому

      ​@@JRK_RIDES It worked. Thank you