Remove K Digits - Leetcode 402 - Python
Vložit
- čas přidán 27. 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/remove-...
0:00 - Read the problem
1:02 - Intuition
9:00 - Drawing Explanation
11:29 - Coding Explanation
leetcode 402
This question was identified as a Meta interview question from here: github.com/xizhengszhang/Leet...
#meta #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
Hey, I almost never comment on yt vids, but I've been studying almost exclusively through your videos for the last 2 months and I just received 3 offers this week 😭. This is life-changing for me, and I can't thank you enough. Please keep up the great work. Will be subscribing to your Patreon, even though I know that doesn't even come close to repaying you for how much you've helped all of us. Thank you so, so much for what you're doing ❤ 🙏
Congrats, best of luck! :)
Congratulations 🙂🎉🎉
Congratulations! Truly amazing! Best wishes on your future endeavors and may all the viewers of this channel learn and reach their dreams!
Congratulations. !!!!
I don't know why but I feel so much joy when you say "yes it does, and it's very efficient". I think these coding problems have gotten to me.
Latest test cases it give TLE, here is the updated one if someone is interested
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
stack = []
for val in num:
while k>0 and stack and stack[-1]>val:
k-=1
stack.pop()
if not stack and val=='0':
continue
stack.append(val)
res = ''.join(stack)
if k>0:
res = res[:len(res)-k]
return res if res else '0'
You dropped this 👑.
@@dagi_works facts🤣🤣
No need to heck if k>0 if it is zero then we would still have the same answer but I guess it would simplify things ofr the interviewer
New test case is failing this code. string is very large So cannot convert to int.
i used while stack and stack[0]=="0":
stack = satck[1:]
or
result = ''.join(stack).lstrip('0')
javascript code for this.
while (answer.length > 0 && answer[0] === '0') answer.shift();
if (answer.length === 0) answer = '0';
else answer = answer.join('');
1. Use the string method lstrip to remove the "0" from the left.
2. A loop and a pointer that run while the num at pointer is equals to "0". and use that index to ignore the leading zeros in the join.
3. instead of a stack, a queue could solve this leading zero issue efficiently while keeping the solution the same.
I can't thank you enough for creating this channel and being such a good teacher! This problem in particular had been too hard for me for a very long time, but this video makes it so much simpler to understand. But in general, watching your videos has actually made me better at algorithms than I ever was and I could see that difference in every interview I give.
Neetcode, you helped me get a job! Thank you so much! Your explanations are the best on youtube!
your videos got me intrested in leetcode/programming.thanks a lot.🙏
Every time you say "Thanks for watching" I feel like saying a heartfelt "Thanks for posting" !!!!! You are awesome !!!
I have been following you for a month. I try to solve a problem and regardless of whether I am able to solve it or not, I watch your videos as it makes me learn something vital.
Do you have any tips to improve the problem solving ability?
This problem literally caused me a headache yesterday , this is not at all medium problem
Great solution and explanation, as always. Thanks for posting the vdo. Keep up the fantastic work!!! looking forward to more :)
Thx neetcode! Your videos really helped me a lot! :)
Your videos are most explained of all the available channels
Thanks for the video solution @NeetCode, as always simple and clear!
One note for Java devs:
In Java parseInt won't work to remove leading zeroes(it throws NumberFormatException) since num could be larger than Integer.MAX_VALUE given the constraints of problem: 1
Great video, I was thinking If there is a possible decision tree/recursive approach that can be used here
When you asked which data structure to use i thought of monotonic stack(because of one your previous videos) ,rn I'm so obsessed with your explanations 😭
Instead of removing the leading zeros at the end, you could just have a condition inside of the loop, that if the stack is empty, and value of c is '0', then just continue to the next iteration of the loop
That's good. Thanks
Thanks for the clear algorithm explaination, it really hepls me a lot >.
you made it so easy....thanks man
Thank you for your explanation !
Phenomenal explanation as always. Thank you
You are my fav teacher, thank you for all
Thank you so much for the explanation, otherwise, I would never have understood the question's expectation. Can you please help me think about how to analyze if the k digits should be removed in a sequence or subsequence? Because it was not clear in the question as well as the sample test cases. What I believe is when a person will fail many test cases or unless given a hint, then he would be able to realize something. What do you think?
Great explanation though! I have a small question: when in the returning statement we are converting the string to int to avoid trailing zeroes, but the size of the string is 10^5, wouldn't that overflow the int limit? [For example in java If I did that then it would make the max value as (2^31 - 1) instead of our actual string] Please advise.
That's a really good point actually, it only works in python because numbers are not limited in bits. But yeah in most languages you would have to handle it differently.
You can use the lstrip function to remove leading zeroes. This way you don't need to convert the string to an integer.
this is awesome explanation, thanks a lot buddy
You can do stack[:-k] (no need for length)
You are such a great soul!
So elegant..kudos..!!
This question was asked in an interview, needless to say I haven't seen it before & its very hard to comp up with an algo like this
Verdict : REJECTED
Amazing. Thank you
Nicely Explained
We can use string instead of stack in languages where stack doesn't exist. So pop becomes removing last element from the string and spend becomes spending to that same string
Please make the videos on all types of algorithms which are use in problem solving dedicated one please.
Thanks NeetCode such a great explantion. Could you please suggest some resources to read about Sytem design and Low level design, I have an upcoming rounds..Thanks and many congratulations for The Google!!
Thanks neetcode for great explanation
I think you forget to edit out 4:09, had me confused for a minute :D
Regardless, great video again thanks for the work you do!
whoops, luckily youtube lets you edit videos after uploading. should be fixed in a couple hours :)
i wanna know how that string(int(res)) works? why didn't it threw out of range exception at higher ranges??
ha ha I just did it yesterday.... and looking for your solution.... here is it 😁
da best explanation like always
logic to strip leading zeros needed to be modified otherwise I am getting below error
ValueError: Exceeds the limit (4300) for integer string conversion: value has 9001 digits; use sys.set_int_max_str_digits() to increase the limit
used the below logic to solve the error
if res:
for i, s in enumerate(res):
if s != '0':
break
return res[i:]
else:
return "0"
@@rideravi6999 another way to do it is not add 0 to the stack if the stack is empty and the character is 0.
you can add this before stack.append(c)
if not stack and c == '0':
continue
Updated last two lines to these to avoid above error:
res = "".join(stack).lstrip("0")
return res if res else "0"
why do we need while? can we not do with if else?
super explanation👍👍
Thank you! 👍👍
Hope this question saves Meta stock 🔥
lol
Thank you so much
Did you know you are "The Godfather" of Teaching coding this consistently
I got the exact same intuition and conceptual approach but i cant implement in code. I found my mistake it was about the unremoved k integers from the back of the number
Thanks!
Best ever!
hi why this piece of code ended with the error of "ValueError: Exceeds the limit (4300) for integer string conversion: value has 9001 digits; use sys.set_int_max_str_digits() to increase the limit
return str(int(res)) if res else '0'" in my console?
these should be the last 2 lines
res = "".join(stack).lstrip("0")
return res if res else "0"
It took me some time to get a sense of the solution.. I think I didn't consider the order of the number cause the order of the number would be the same. The key points I understood is that getting rid of big nth numbers in front of the number because it leads to reduce the total number. and the k part is when there is still k numbers to delete left. We simply delete the last k elements because if they are bigger than the front of numbers, it would have been deleted by the logic in the loop. So it deletes k numbers from the rare. This is what I understood, Is it alright?
I tried to come up with a solution using recursion but its not that efficient was able to run only half the testcases before running into tle:
class Solution:
def helper(self, num, k, res = []):
if k == 0:
if num:
res.append(int(num))
else:
res.append(0)
return
for i in range(len(num)):
if i!=len(num) - 1:
self.helper(num[0:i] + num[i+1:], k-1, res)
else:
self.helper(num[0:-1], k-1, res)
return str(min(res))
def removeKdigits(self, num: str, k: int) -> str:
res = []
return self.helper(num, k, res)
Hard thing is to come up with algorithm / logic
The tags in thumbnail are from leetcode premium?😅
10:03 You should have said "non-decreasing order" instead of "increasing order". That's how leetcode frames the question.
3:59 Didn't knew Neetcode is german
Hi NeetCode, this is my solution:
would this work?
def remove_k_digits(nums, k):
if len(nums) 0:
removal_stack = []
for i in range(len(nums)):
d_remove = nums[:i] + nums[i+1:]
removal_stack.append(d_remove)
max_val = min(removal_stack)
idx = removal_stack.index(max_val)
nums = nums[:idx] + nums[idx+1:]
k -= 1
return str(int(nums))
Is the time complexity n^2 because of while loop
no. its just O(N) . Overall we are traversing the string and stack only once.
Can you do leetcode 828??
isnt the smallest number 1122 in the solve example thou
Easy to solve intuitively but hard to implement.
the best
Alternative:
if the goal is to remove K digits to find the lowest value, then we can rephrase this as:
- find the subsequence of length solutionLen = N - K which represents the smallest numeric value
Then we can implement this by iterating (N-K times) by selecting the smallest value from left up to some maximum ending index, where max ending index is calculated to be N - solutionLen + i (where i is our iteration index)
In each iteration we select the smallest value and its corresponding index, and then enter the next iteration to search for the next minimum value, starting with the last iteration's corresponding idx.
This has naievely N squared time complexity, but we can use a segment tree to efficiently get minimums in a segment, so that our minimum search aborts early (in constant time aggregated).
How did you know I was desperately searching for this problem from yesterday
Awesome
UPDATE: As of 2024 April 11, That conversion to an int and back to a string will not work. Instead, you can use "res = res.lstrip("0")" to remove all the leading zeros from the string. Just in case you're trying that last line and wanna rip your hair out when it doesn't work!
I kept getting the error:
ValueError: Exceeds the limit (4300 digits) for integer string conversion: value has 9001 digits; use sys.set_int_max_str_digits() to increase the limit
Had to fix it by including:
import sys
sys.set_int_max_str_digits(0)
I'm surprised that the test cases passed for you without having to encounter this error.
:/
He solved it 2 years ago so back then there might have been less test cases
doing it manually after the for loop solved it for me:
#if k>0, then remove k elements from right/end.
while k>0 and stack:
stack.pop()
k-=1
#if there are leading zeros.
while stack and stack[0]=="0":
stack.pop(0)
res = "".join(stack)
return res if res else "0"
the code is not working
ValueError: Exceeds the limit (4300) for integer string conversion: value has 9001 digits; use sys.set_int_max_str_digits() to increase the limit
return str(int(res)) if res else "0"
Line 15 in removeKdigits (Solution.py)
ret = Solution().removeKdigits(param_1, param_2)
Line 43 in _driver (Solution.py)
_driver()
Line 54 in (Solution.py)
what to do ?
these should be the last 2 lines
res = "".join(stack).lstrip("0")
return res if res else "0"
man i feel so dumb everytime i see these leetcode videos, i'll never have a good job =/
Runtime error
ValueError: Exceeds the limit (4300 digits) for integer string conversion: value has 9001 digits; use sys.set_int_max_str_digits() to increase the limit
^^^^^^^^
return str(int(res)) if res else "0"
Line 11 in removeKdigits (Solution.py)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ret = Solution().removeKdigits(param_1, param_2)
Line 35 in _driver (Solution.py)
_driver()
Line 46 in (Solution.py)
stack = []
for c in num :
while k > 0 and stack and stack[-1] > c:
k -=1
stack.pop()
stack.append(c)
stack = "".join(stack[:len(stack)-k])
return stack.lstrip("0") or "0"
is my logic valid please help me to fix it .......
am i in right direction ?
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
if k >= len(num):
return '0'
m = float('inf')
for i in range(len(num)):
x = int(num[:i] + num[i+k:])
m = min(m, x)
m = str(m)
return m if m else '0'
Java Solution:
class Solution {
public String removeKdigits(String num, int k) {
if(num.length()==k) return "0";
ArrayDeque stk = new ArrayDeque();
for(int i=0;i (val-'0') && k>0){
stk.pop();k--;
}
stk.push(val);
}
String res="";
while(!stk.isEmpty() && k>0){stk.pop();k--;} //k still >0 so remove big nums
while(!stk.isEmpty()){res=stk.pop()+res;}
while(res.length()>1 && res.charAt(0)=='0')
{res=res.substring(1,res.length());} //remove leading 0s
return res;
}
}
I have a coding test in some days if you can help i will pay! 3 problems easy medium hard need help for medium and hard