Remove K Digits - Leetcode 402 - Python

Подписаться 764 тыс.

Просмотров 59 тыс.

50% 1

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

Наука

Опубликовано:

26 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 100

@CJ-ot2pg 2 года назад

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 2 года назад

Congrats, best of luck! :)

@NeetCode 2 года назад

Congratulations 🙂🎉🎉

@sumosam1980 2 года назад

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

@kigarde 2 года назад

Congratulations. !!!!

@rxpt0rs 2 года назад

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.

@user-kt4gp5fb8q 3 месяца назад

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 3 месяца назад

You dropped this 👑.

@hen56349 Месяц назад

@@dagi_works facts🤣🤣

@user-fk1zp5gk1o 25 дней назад

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

@chinesemimi 2 года назад

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

@BarneyBing883 2 года назад

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.

@killpointx 3 месяца назад

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 3 месяца назад

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

@akurabravery1810 3 месяца назад

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.

@vdyb745 2 года назад

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

@VrickzGamer 2 года назад

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

@shubhamsantoki5265 2 года назад

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

@chagsssss 2 года назад

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?

@chaengsaltz829 2 года назад

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

@xianweiwu1843 7 месяцев назад

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

@VrickzGamer 2 года назад

Your videos are most explained of all the available channels

@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

@nammi895 2 месяца назад

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

@abhishekseth7187 11 месяцев назад

you made it so easy....thanks man

@Gustavo-ve9hr 2 года назад

Thank you for your explanation !

@SairamDasari2000 6 месяцев назад

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 😭

@user-xi6jz3fb4u Год назад

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

@mehrdadmirpourian64 2 года назад

Amazing. Thank you

@vinaypawde9894 2 года назад

So elegant..kudos..!!

@MP-ny3ep 3 месяца назад

Phenomenal explanation as always. Thank you

@hoangvietng7100 3 месяца назад

You are my fav teacher, thank you for all

@jaatharsh 3 месяца назад

this is awesome explanation, thanks a lot buddy

@haroldobasi2545 2 года назад

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

@shashankgarg7476 Год назад

You are such a great soul!

@amanavengeraman 2 года назад

Nicely Explained

@user-rv1bx8hx4v 3 месяца назад

Thank you! 👍👍

@alokesh985 2 года назад

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 2 года назад

That's good. Thanks

@johnj171 2 месяца назад

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

@krateskim4169 3 месяца назад

Thank you so much

@sharksinvestment9864 Год назад

Thanks neetcode for great explanation

@pawananubhav12 2 года назад

da best explanation like always

@ajayjangid1164 10 месяцев назад

super explanation👍👍

@vijethkashyap151 3 месяца назад

Best ever!

@andreytamelo1183 2 года назад

Thanks!

@annbrown8069 2 года назад

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?

@andrepinto7895 2 года назад

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

@nishantingle1438 2 года назад

Hope this question saves Meta stock 🔥

@NeetCode 2 года назад

lol

@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

@__________________________6910 2 года назад

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

@jenishsoni10 2 года назад

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 2 года назад

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 2 года назад

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

@pollathajeeva23 2 года назад

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

@ChandraShekhar-by3cd 2 года назад

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

@FCBarcelonaXMI 2 года назад

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 2 года назад

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

@prathamtyagi5914 Год назад

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

@ravindrabhatt 2 года назад

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

@rideravi6999 11 месяцев назад

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 11 месяцев назад

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 11 месяцев назад

@@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 4 месяца назад

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

@samarthjain5015 3 месяца назад

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

@raidyqk 3 месяца назад

3:59 Didn't knew Neetcode is german

@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

@krishnakshirsagar4570 2 года назад

Hard thing is to come up with algorithm / logic

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

@VarunSharma-xd8xd 3 месяца назад

the best

@09sangram Год назад

Awesome

@licokr 3 месяца назад

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?

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

@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 9 месяцев назад

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

@syedaqib2912 2 года назад

The tags in thumbnail are from leetcode premium?😅

@JLSXMK8 3 месяца назад

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!

@akashverma5756 9 месяцев назад

Easy to solve intuitively but hard to implement.

@VrickzGamer 2 года назад

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

@jugsma6676 2 года назад

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

@managerbmr 2 года назад

Can you do leetcode 828??

@midhileshmomidi3120 2 года назад

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.

@lakshaygupta5268 10 месяцев назад

isnt the smallest number 1122 in the solve example thou

@thejasnaik4694 3 месяца назад

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 3 месяца назад

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

@chuckle_pugz96 3 месяца назад

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"

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

@vishaalkumaranandan2894 3 месяца назад

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 3 месяца назад

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"

@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 9 месяцев назад

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

@ASWANTHMANCHALA 3 месяца назад

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'