The Number of Beautiful Subsets - Leetcode 2597 - Python

[@NeetCodeIO]

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]

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]

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]

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]

I like seeing both simple and optimal solutions!

[@kevinwang8632]

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]

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.😂

[@Pegasus02Kr]

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

[@MP-ny3ep]

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

[@jagrutiisantosh]

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.

[@carrotiq6879]

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.

[@jotrades26]

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]

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.

[@ChiragMalaviya-so7tw]

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

[@ap2s2000]

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

[@NeetCodeIO]

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

[@ap2s2000]

@@NeetCodeIO Got it, thanks

[@sourvad]

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

[@pastori2672]

great explanation man i actually understood the optimal solution this time

[@OrphanedZombie]

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

[@sahilhedau7377]

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

[@rjarora]

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

[@prasunroy2802]

Thank you

[@joydeeprony89]

bro back after long time

[@brokecoder]

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

[@shivkrishnajaiswal8394]

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

[@nikhil199029]

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

[@varunpalsingh3822]

thank you 🙂

[@rostyslavmochulskyi159]

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

[@irabucc469]

That's so elegant

[@mohaimenchowdhury]

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.

[@EduarteBDO]

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

[@Perry-tf2pr]

insane

[@MadhuSanduri]

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

[@albedo9617]

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

[@donalshijan5615]

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.

[@IntelliStar_]

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

[@DeathSugar]

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

[@moabd7575]

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]

nvm, i passed hash map by reference and it worked

[@kgCode658]

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

[@jaatharsh]

we need both simple + optimal

[@Antinormanisto]

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

[@MohanRam-mq2pk]

bro try to be consistent

[@akash-kumar737]

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

[@kgCode658]

point😆

[@anay-208]

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]

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

[@anay-208]

@@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 KZbin 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

[@asifiqbal21]

Does anybody expect the optimal solution in an interview?

[@michael._.]

[@albedo9617]

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]

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]

​@@JRK_RIDES It worked. Thank you