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 ❤ 🙏
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'
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')
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.
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 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.
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?
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
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
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 😭
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
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
@@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
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.
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).
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"
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?
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?
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)
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?
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 ?
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. :/
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)
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!!
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
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 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'
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. !!!!
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
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.
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.
Neetcode, you helped me get a job! Thank you so much! Your explanations are the best on youtube!
Every time you say "Thanks for watching" I feel like saying a heartfelt "Thanks for posting" !!!!! You are awesome !!!
This problem literally caused me a headache yesterday , this is not at all medium problem
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!
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
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.
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?
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
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
Your videos are most explained of all the available channels
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 😭
Did you know you are "The Godfather" of Teaching coding this consistently
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
10:03 You should have said "non-decreasing order" instead of "increasing order". That's how leetcode frames the question.
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"
your videos got me intrested in leetcode/programming.thanks a lot.🙏
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.
Hope this question saves Meta stock 🔥
lol
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).
You are my fav teacher, thank you for all
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 :)
Great video, I was thinking If there is a possible decision tree/recursive approach that can be used here
You can do stack[:-k] (no need for length)
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"
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?
ha ha I just did it yesterday.... and looking for your solution.... here is it 😁
Phenomenal explanation as always. Thank you
Thanks neetcode for great explanation
3:59 Didn't knew Neetcode is german
Thx neetcode! Your videos really helped me a lot! :)
Hard thing is to come up with algorithm / logic
this is awesome explanation, thanks a lot buddy
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"
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)
Bro you are the legend🐐
Thanks for the clear algorithm explaination, it really hepls me a lot >.
Great solution and explanation, as always. Thanks for posting the vdo. Keep up the fantastic work!!! looking forward to more :)
you made it so easy....thanks man
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?
You are such a great soul!
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"
Nicely Explained
Thank you for your explanation !
Please make the videos on all types of algorithms which are use in problem solving dedicated one please.
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"
super explanation👍👍
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;
}
}
da best explanation like always
So elegant..kudos..!!
Thank you so much
Best ever!
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!!
Amazing. Thank you
How did you know I was desperately searching for this problem from yesterday
Easy to solve intuitively but hard to implement.
i wanna know how that string(int(res)) works? why didn't it threw out of range exception at higher ranges??
The tags in thumbnail are from leetcode premium?😅
Thanks!
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
why do we need while? can we not do with if else?
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))
the best
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'
Awesome
isnt the smallest number 1122 in the solve example thou
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.
man i feel so dumb everytime i see these leetcode videos, i'll never have a good job =/
Can you do leetcode 828??
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
Thank you! 👍👍