Remove K Digits - Leetcode 402 - Python

[@CJ-ot2pg]

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 ❤ 🙏

[@mikeyfeeney4294]

Congrats, best of luck! :)

[@NeetCode]

Congratulations 🙂🎉🎉

[@sumosam1980]

Congratulations! Truly amazing! Best wishes on your future endeavors and may all the viewers of this channel learn and reach their dreams!

[@kigarde]

Congratulations. !!!!

[@AvijeetRanawat]

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'

[@dagi_works]

You dropped this 👑.

[@hen56349]

@@dagi_works facts🤣🤣

[@IbrahimLaeeq-v2g]

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

[@rxpt0rs]

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.

[@killpointx]

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

[@licokr]

javascript code for this. while (answer.length > 0 && answer[0] === '0') answer.shift(); if (answer.length === 0) answer = '0'; else answer = answer.join('');

[@akurabravery1810]

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.

[@chinesemimi]

Neetcode, you helped me get a job! Thank you so much! Your explanations are the best on youtube!

[@VrickzGamer]

This problem literally caused me a headache yesterday , this is not at all medium problem

[@nammi895]

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

[@vdyb745]

Every time you say "Thanks for watching" I feel like saying a heartfelt "Thanks for posting" !!!!! You are awesome !!!

[@BarneyBing883]

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.

[@chagsssss]

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?

[@mykytapiskarov7291]

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

[@alokesh985]

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

[@nguyenhoanvule5755]

That's good. Thanks

[@JLSXMK8]

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!

[@SairamDasari2000]

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 😭

[@VrickzGamer]

Your videos are most explained of all the available channels

[@shubhamsantoki5265]

your videos got me intrested in leetcode/programming.thanks a lot.🙏

[@anjanobalesh8046]

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

[@rideravi6999]

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]

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"

[@leeroymlg4692]

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

[@monicatare6536]

Updated last two lines to these to avoid above error: res = "".join(stack).lstrip("0") return res if res else "0"

[@jenishsoni10]

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.

[@NeetCode]

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.

[@anishdeshmukh4690]

You can use the lstrip function to remove leading zeroes. This way you don't need to convert the string to an integer.

[@haroldobasi2545]

Great video, I was thinking If there is a possible decision tree/recursive approach that can be used here

[@samarthjain5015]

10:03 You should have said "non-decreasing order" instead of "increasing order". That's how leetcode frames the question.

[@johnj171]

Did you know you are "The Godfather" of Teaching coding this consistently

[@hoangvietng7100]

You are my fav teacher, thank you for all

[@nishantingle1438]

Hope this question saves Meta stock 🔥

[@NeetCode]

lol

[@xybnedasdd2930]

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

[@andrepinto7895]

You can do stack[:-k] (no need for length)

[@annbrown8069]

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?

[@MP-ny3ep]

Phenomenal explanation as always. Thank you

[@__________________________6910]

ha ha I just did it yesterday.... and looking for your solution.... here is it 😁

[@licokr]

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?

[@sharksinvestment9864]

Thanks neetcode for great explanation

[@FCBarcelonaXMI]

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!

[@NeetCode]

whoops, luckily youtube lets you edit videos after uploading. should be fixed in a couple hours :)

[@xianweiwu1843]

Thx neetcode! Your videos really helped me a lot! :)

[@krishnakshirsagar4570]

Hard thing is to come up with algorithm / logic

[@jaatharsh]

this is awesome explanation, thanks a lot buddy

[@shashankgarg7476]

You are such a great soul!

[@ajinkyapahinkar6463]

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)

[@rojo_pes75]

Bro you are the legend🐐

[@raidyqk]

3:59 Didn't knew Neetcode is german

[@amanavengeraman]

Nicely Explained

[@宮水三葉の老公]

Thanks for the clear algorithm explaination, it really hepls me a lot >.

[@abhishekseth7187]

you made it so easy....thanks man

[@prathamtyagi5914]

i wanna know how that string(int(res)) works? why didn't it threw out of range exception at higher ranges??

[@anonymy834]

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?

[@beonthego8725]

these should be the last 2 lines res = "".join(stack).lstrip("0") return res if res else "0"

[@Gustavo-ve9hr]

Thank you for your explanation !

[@pollathajeeva23]

Please make the videos on all types of algorithms which are use in problem solving dedicated one please.

[@ajayjangid1164]

super explanation👍👍

[@ravindrabhatt]

why do we need while? can we not do with if else?

[@chaengsaltz829]

Great solution and explanation, as always. Thanks for posting the vdo. Keep up the fantastic work!!! looking forward to more :)

[@vinaypawde9894]

So elegant..kudos..!!

[@thanirmalai]

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

[@akashverma5756]

Easy to solve intuitively but hard to implement.

[@thejasnaik4694]

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. :/

[@BurhanAijaz]

He solved it 2 years ago so back then there might have been less test cases

[@chuckle_pugz96]

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"

[@pawananubhav12]

da best explanation like always

[@krateskim4169]

Thank you so much

[@mehrdadmirpourian64]

Amazing. Thank you

[@vijethkashyap151]

Best ever!

[@ChandraShekhar-by3cd]

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!!

[@SANJAYSINGH-jt4hf]

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; } }

[@syedaqib2912]

The tags in thumbnail are from leetcode premium?😅

[@andreytamelo1183]

Thanks!

[@jugsma6676]

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

[@midhileshmomidi3120]

Is the time complexity n^2 because of while loop

[@nityanandbhaskar2155]

no. its just O(N) . Overall we are traversing the string and stack only once.

[@vishaalkumaranandan2894]

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)

[@shashivish2022]

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"

[@lakshaygupta5268]

isnt the smallest number 1122 in the solve example thou

[@VrickzGamer]

How did you know I was desperately searching for this problem from yesterday

[@managerbmr]

Can you do leetcode 828??

[@VarunSharma-xd8xd]

the best

[@ASWANTHMANCHALA]

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'

[@infoknow3278]

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 ?

[@beonthego8725]

these should be the last 2 lines res = "".join(stack).lstrip("0") return res if res else "0"

[@09sangram]

Awesome

[@cfbf96]

man i feel so dumb everytime i see these leetcode videos, i'll never have a good job =/

[@krishnakshirsagar4570]

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

[@NursultanBegaliev]

Thank you! 👍👍