Delete and Earn - Dynamic Programming - Leetcode 740 - 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 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: leetcode.com/problems/delete-...
0:00 - Read the problem
3:10 - Explain Intuition
7:12 - Explain DP Solution
12:50 - Coding Explanation
leetcode 740
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#dynamic #programming #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
Even though this is a "medium" in leetcode, this guy makes every coding problem seem like an easy one. Hey man, you've got such great teaching skills. Thank you for sharing your algo approaches here. This channel is definitely gold.
I have a couple of coding interviews coming later this month. Not expecting much since I pretty much just started relearning a few weeks back but emulating and learning from your explanations and solutions helped me learn more in those couple of weeks than I have in months of bruteforcing LC back in college.
Ty! np: sorted() converts the set of nums array to the list in Python; can skip list() function of line #4
why do we only need to look at the two previous values? couldn't values before then change depending on which current value we choose?
sooo elegant - thank you!!
HI, i don't know if you are answering but i am not getting the idea of the start of the operations, like when we have earn1 = 0 and earn2 = 0, i am trying to imagine it as a dp list and apply it but lost
Thanks. More videos will be appreciated 🙂
wow..You gave a very good hint which made me solve the problem without watching the solution .. Anyways watched the solution after solving..Thank you very much for your efforts
Amazing explanation!
Brilliant explanation. Thanks for this.
No problem 👍
did the recursive solution on my own but optimising this is tough
Amazing Explaination !
This is by far one of the best DP explanations, thanks so much!
man, you are everywhere!!
in 5 min of a video i was able to code it my self
This is an exceptionally well taught lesson
Thank you!
I implemented a sub-optimal solution using hashmap and set which worked for 50% of the testcases but when you said it is similar to house robber, a light-bulb went off in my head!! You're a real G!
Dear Neetcode - why did you sort your array? And why did the DP function not include numbers greater than the selected value (like n+2, n+3, etc)
So that we can track the n-1 numbers easily. Also at every index we maintain the max value.
Thanks !
@ time stamp 12:48 you told you over complicated it up! Bruhh Nooo you did not! It was pristine!
Was this question inspired by someone on your discord?
Yeah, I wanted to do it much sooner... but better late than never :)
LLLLLLLOVE this explanation!!!!!!
another small improvement would be to consider i = 0 as a base case, i.e. fill out earn1 as 0 and earn2 as nums[0] * counts[nums[0]], then start iterating from i = 1
Hey I'm new to leetcode
I recently found your channel
I do solve easy problems by following your explanation
But it seems I tend to forget the problem that I solved within a week
How to retain the concepts that you teach in every video?
Hi, I was facing the same problem beforehand. Any coding problem has 2 things: intuition and coding.
You only have to remember the intuition. Once you are able to understand it, coding is no big deal !
@@mrditkovich2339 hey thanks for the suggestion
These days I started to write down those algorithms in my notebook then execute them in code
Now I'm feeling far better
@@roadtomillion9499 Glad to hear ! As an addition, please prefer quality over quantity. Most of the questions related to graph and DP follow a pattern.
@@roadtomillion9499
I also recommend following with the Spaced Repetition System in order to revisit what you have solved.
Hey, Can you please also mention the Time and Space complexity of the final solution in your videos....Interviewers generally ask for it.
Thanks.
Hey, the time complexcity is nlogn because we are sorting and traversing through the array once and space is complexity is 2n one of dictionary and other for array but if we take big oh then it is n. Hope it helps.
good explanation
Amazing
Mr NeetCode, how can we ever achieve your level of intuitive understanding of algorithms, dynamic programming, and the like? Where should we look?
Just practice
If we have [2,3,5] and we choose 5, won't we get 5 + 3 + 2 =10? from your method and leetcode would say is only 8.
you cannot add 2,3 since 3-1=2
I'm surprised you're not sharing the time optimal solution, the O(n) version instead of the O(nlogn) one
How nlogn
@@AshutoshKumar-es8xy sorting was used
Instead of commenting meaningless information, publish it
A year passed and you haven’t provided the o(n) solution
If I get into faang, you deserve my first salary lol. such a quality explanation
I'll atleast meet him and give me a hug.
damm
that was such a good explanation
i really like ur explaining method but the thing is i and most beginner cp enthusiast code in c++ this creates a prblm for all of us if u can code in c++ that will be really helpfull for us thanks btw
Guys I find it very discouraging when I cannot figure out a DP problem. I want to be able to make base cases but some of the questions just have this weird trick.. Is it just me ?
Leetcode weekly 402, almost similar question came (Q3)
🔥🔥🔥
only if this dude coded in c++
it seems unnecessary to make nums into a set -- if you are going to use a Counter() you get a set out of the keys anyway
sorting is the key lol
for(int i=2;i
man!!! i wasted like 3-4 hours and the mistake was i didn't put == inside the if statement and it didn't even show an error.
Can you please share your complete code? I am getting 47 where it should be 37
@@bidishadas832 Here you go. It isn't concise tho because I was a noob back then.
class Solution{
public:
int deleteAndEarn(vector& nums){
if(nums.size()==1) return nums[0];
if(nums.size()==2){
sort(nums.begin(),nums.end());
if(nums[0]+2>=nums[1]) return (nums[0]+nums[1]);
else if(nums[0]==nums[1]) return 2*nums[0];
else if(nums[0]+1==nums[1]) return nums[1];
}
map m;
for(int i=0;i
Once he draws a recursion tree i can write a recursive code
The fact You have to know that You need to sort it first and then eliminate duplicates is ludicrous. How on this earth is anyone supposed to come up with that? it's just guessing
I am Stupid