Very comprehensive problem to practice stacks! Together with asteroid collision and daily temps, one can argue understanding those 3 problems alone are a solid prep for stack problems on interviews.
@Iamnoone56
2 жыл бұрын
this was asked in my amazon sde 1 interview somehow i managed t solved it. holy cow!
@xinli7477
2 жыл бұрын
Wow, they ask such difficult questions for sde 1? Congrats on solving it!
@PP-pe3fs
Жыл бұрын
You have my respect
@gazijarin8866
Ай бұрын
The fact that you appended the string AFTER the pop made the problem so easy. I was shaking my head in horror trying to reverse the string once after appending it.
@ShivangiSingh-wc3gk
2 жыл бұрын
Did this myself and came to see the solution. I am so happy to see my progress. Thank you soooo much!!!
@harishsn4866
2 жыл бұрын
I know you probably hear this a lot but your explanations are so clear and easy to grasp. Thanks a ton for this.
@CostaKazistov
2 жыл бұрын
It's no wonder Google hired him in a heartbeat. NeetCode has a great talent for reducing complex problems into simplest and digestible way.
@amogchandrashekar8159
3 жыл бұрын
You make things feel so easy! Thank you so much 😀
@varunshrivastava2706
2 жыл бұрын
Then maybe its just me who still didn't understood it.
@victoronofiok520
2 жыл бұрын
@@varunshrivastava2706 I would ask that you watch it again if so and jott what you can as you follow along Bless🙏
@deathbombs
Жыл бұрын
Great explanation and diagrams!! This is what I got: The things to decode have this pattern: Coefficient(content) 2 things needed:coefficient, and content My approach using stack was adding just the {}, and tracking the indexes for substring , but I like your approach is cleaner by adding everything to stack. General approach: for all chars in string if stack is Empty: if isDigit: calculate the numerical part/coefficient, if (, add to stack, save startindex if is character, add to string builder if stack is not empty: add everything if is ), remove from stack if stack is empty, recursively call helper(s.substring(startIndex+1, endIndex)
@susmi51910
3 жыл бұрын
You explain these problems so well! can you please do a video on the problem " Guess the word" ?
@shubhamshrivastava8649
2 жыл бұрын
Amazingly explained, was able to implement without even looking at code. Thank you!
@begenchorazgeldiyev5298
2 жыл бұрын
I don't know why I am still using java. I came up with the same solution with a stack but it is at least twice longer thanks to java. This is so easy to read and comprehend.
@utsavshrestha7162
2 жыл бұрын
Lol same bro. Python is the best language for interviews in my opinion.
@LeetCodeSimplified
Жыл бұрын
According to LeetCode premium, the time complexity of this solution is actually O(maxK^countK * n), where maxK is the maximum value of k, countK is the count of nested k values and n is the maximum length of the encoded string. Example, for s = 20[a10[bc]], maxK is 20, countK is 2 as there are 2 nested k values (20 and 10). Also, there are 2 encoded strings a and bc with the maximum length of the encoded string n as 2.
@kylefan8478
2 жыл бұрын
this is a very good explanation, very concise and clear code. I implemented this in C++ and got 100% time and 96% memory.
@watchlistsclips3196
2 жыл бұрын
please send me cpp code i am getting wrong answer in one test case
@watchlistsclips3196
2 жыл бұрын
This is my code: class Solution { public: string stuff(int n,string s) { string t; while(n--) t+=s; return t; } int stringToNum(string s) { int num=0; for(int i=0;i
@SriHarishPopuri
21 күн бұрын
The sub string calculation in this solution (which is done twice btw) is a costly operation to do, both in time and space. Strings are immutable and this above way of calculating substrings can lead to quadratic time complexity when calculating the multiplier or inner string between square brackets, when there are large inputs. Instead, the characters can be appended to a list and joined using "".join(list) method, which will have linear time complexity. Thats a lot better in terms of the time and space complexities.
@AnupBhatt
2 жыл бұрын
First coding channel on KZitem that I put the bell icon to receive all updates for !!
@CostaKazistov
2 жыл бұрын
Same
@carloscarrillo201
2 жыл бұрын
You are coding god, man. You're in my idol list, right next Van Halen!
@thndesmondsaid
26 күн бұрын
aw man, tried this on my own and thought to use a stack but couldn't figure out the algo. Thank you!
@arghya_0802
Жыл бұрын
One of the best solution availabe on YT. Great work sir. Huge fan of the way you break tough and/or complex problems into simpler versions!!😍😍
@kashishshukla23
2 жыл бұрын
Best explanation man! TYSM for your efforts.
@saifmohamed1776
3 жыл бұрын
i think if we consider the length of the output string is K then the time complx will be linear in this length K -> O(k) ;
@ren-hauchuang2005
2 жыл бұрын
This is the way better solution than official ones
@brandenimmerzeel8182
2 ай бұрын
Thanks, i ended up solving this with recursion on my first attempt. I used this video to learn how to apply stacks to the problem. Thank you.
@adityavikrant3847
23 күн бұрын
Great solution! Could you explain why we need to check whether the stack exists before popping digits?
@jinny5025
3 жыл бұрын
Best explanation as always!
@yondensawyers2778
Жыл бұрын
I solved this a different way in linear time by using two stacks; one of factors where the top of the stack is the last number for the characters and another stack containing the substrings. whenever a ] character is detected it pops the two from their respective stacks, multiplies them, then appends it to the next top of the characters stack.
@sudoaptinstallrana9572
10 ай бұрын
can you share your solution i am thinking in the same way
@iamcarlostovias
8 күн бұрын
This was my original intuition as well.
@Gnaneshh
2 жыл бұрын
Terrific explanation!!
@prafulparashar9849
2 жыл бұрын
Great explanation !! I was wondering whether we can do it solely by recursion calls?
@Cloud-577
2 жыл бұрын
yes you can
@october3518
Жыл бұрын
wow usually I feel a bit anxious when not able to come up with a soln, I have been watching ur few vids! explanations r crisp and easy to understand, I even like it's in python while I code in cpp lol
@bumpin7789
2 жыл бұрын
How long do you actually take to solve these questions for the first time? It seems to take more than 1.5hrs for me.
@k999ford
Жыл бұрын
Is there a reason you always do range(len(s)) instead of for x in s or enumerate(s)? I've been watching a lot of of these (great) videos and I noticed that, so I'm wondering...
@cherylto5898
9 ай бұрын
Love your videos, the clearest explainations I've come across among all the other ones ... Keep it up!
@ashutosh1541
2 жыл бұрын
Man this is so easy in python .. i was doing it in C++ . i had the same logic but implementation was so tough for it
@pif5023
5 ай бұрын
Great video! Thanks! This problem showed me stacks are amazing for accruing and backtracking in an organic way!
@amitupadhyay6511
3 жыл бұрын
I did everything same except : substr+=stack.pop() and finally, substr=substr[::-1] and similar for k how m i am failing a test case. Could you please explain the difference ? Failed test case:"3[z]2[2[y]pq4[2[jk]e1[f]]]ef"
@chenhaibin2010
2 жыл бұрын
I guess you essentially have substr = substr + pop instead of pop + substr, so the order of letters are not the same.
@watchlistsclips3196
2 жыл бұрын
I even getting the wrong answer in cpp with the same test you failed.Please tell where i did wrong. class Solution { public: string stuff(int n,string s) { string t; while(n--) t+=s; return t; } int stringToNum(string s) { int num=0; for(int i=0;i
@samridhshubham8109
11 ай бұрын
A very excellent problem and explanation!
@wangyex
Жыл бұрын
This is actually the best tutorial I found on the internet
@satya00155
10 ай бұрын
much easier to understand than upvoted solutions which I could never do interview.
@atulkumar-bb7vi
Жыл бұрын
Explanation put very simple way, thanks for this!
@joydeep_
Ай бұрын
Phenomenal explanation!!
@chenhaibin2010
2 жыл бұрын
Great clear explanation as always. thanks
@arun-ph9cn
Жыл бұрын
WOW. the solution and explanation is simply superb!!
@kakdi77
2 жыл бұрын
Thanks for the video. Can you also do the Encode verion of this the (Leetcode 471) ?
@nemesis_rc
3 жыл бұрын
Well explained.
@dipeshprajapat1203
Жыл бұрын
Your way of explanation awsome
@ethanwong2272
2 жыл бұрын
It's much easier to write it in Python than in Java.
@CostaKazistov
2 жыл бұрын
And even easier in Kotlin 😉
@andrewpaul6251
Жыл бұрын
It seems leetcode added a testcase and this code no longer works
@kazirafidraiyan2553
Жыл бұрын
**This Works** class Solution: def decodeString(self, s: str) -> str: out_str = [] digit = 0 for i in range(len(s)): if s[i] != "]": out_str.append(s[i]) if s[i].isdigit(): digit += 1 else: sub_str = "" while out_str[-1] != "[": sub_str = out_str.pop() + sub_str out_str.pop() n = "" while out_str and out_str[-1].isdigit(): n = out_str.pop() + n n = int(n) out_str.append(int(n)*sub_str) if digit == len(s): return "" else: return "".join(out_str)
@boybi612
2 жыл бұрын
very neat code
@tynshjt
8 ай бұрын
is there another way to solve this without using Stack?
@abhitripathi
Жыл бұрын
You are amazing, Thanks a lot Lots of love
@everydaylifeisgood
Жыл бұрын
I was giving this problem for google's phone interview today. I didn't do as well :(
@nanyangbuyuweng
Жыл бұрын
I don't think the code can cover the corner case as "3"
@ksanjay665
Жыл бұрын
This was asked in Zoho software developer role
@Gaurav-ln8ze
Жыл бұрын
Thank you so much sir for your great and clear explanation. Here the code in c++ :- class Solution { public: string decodeString(string s) { string ans="", substr="", k; int n=s.size(); stack st; for(int i=0; i
@ekanshsharma1309
Жыл бұрын
thank you so much sir for this amazing explaination🙇♂❤
@denni4070
2 жыл бұрын
Just got this for a new grad position and I failed it miserably, should have watched more vids :(
@matthewb2133
Жыл бұрын
great video, thanks
@willcoomans9674
3 ай бұрын
what is the space complexity?
@Cloud-577
2 жыл бұрын
recursive is same as maintaining our own stack
@naodtewodrosasregdew2782
10 ай бұрын
GOAT
@hhcdghjjgsdrt235
Жыл бұрын
stack makes this problem pretty much easier
@crazier192
2 жыл бұрын
The example showed with 54[ab] which has a 2 digits number. But the solution doesn't account for it. Hope you have time to update the video.
@CostaKazistov
2 жыл бұрын
Actually it does. Line 15 while loop builds a string which then gets converted to Int on Line 17.
@crazier192
2 жыл бұрын
@@CostaKazistov Thank you! It's my bad, sorry.
@nagendrabommireddi8437
2 жыл бұрын
thank you sir
@ryanc1663
3 жыл бұрын
Thanks bro u the man
@dohunkim2922
2 жыл бұрын
the part where you did “while stack and stack[-1].isdigit():” kinda confuses me. Isn’t the stack always nonempty? There always has to be an integer in front of ‘[‘, otherwise we don’t even need to use brackets. Validating whether the stack is empty or not doesn’t seem to be necessary, but the code doesn’t work if I don’t validate it. I’m so lost here
@D_T244
2 жыл бұрын
If our input is "23[a]", when we get to line 15 our stack will contain just [2, 3], we have to keep popping numbers but we need to stop once the stack is empty else we'll get an index error when doing stack[-1].isdigit() check. The isdigit() check catches the following case: input = 23[a4[b]] then our stack will be [2, 3, [, a, 4] when we get to that line 15, isdigit() will make sure we don't pop past the number 4 for the current substring we're building.
@dohunkim2922
2 жыл бұрын
@@D_T244 ohh i didnt consider the case where the integer is a 2digit number. Thansk!!
@thanirmalai
Жыл бұрын
Amazing explanation but i cant think of why i cant solve it by myself
@edwardteach2
3 жыл бұрын
U a God
@MeetManga
2 жыл бұрын
should line 16: k = stack.pop() * 10 +k ?
@CostaKazistov
2 жыл бұрын
Then the digits of K number would be in the wrong order. Popping from the stack retrieves the digits in reverse order. Stepping it through in a debugger makes it easy to see.
@harshitrathore1744
2 жыл бұрын
Very Nice Explanation. Thanks, Buddy...
@rahulpothula1902
Жыл бұрын
my c++ solution(same logic as explained in the video): class Solution { public: string decodeString(string s) { stack stk; string str = ""; for(auto it: s) { if(it >= 'a' and it = '0' and it = "0" and stk.top() 0) counts = stoi(count); for(int i = 0; i < counts - 1; i++) str += str1; stk.push(str); } } string ans = ""; while(!stk.empty()) { ans = stk.top() + ans.substr(0, ans.length()); stk.pop(); } return ans; } };
@YohannesAsfaw-b8b
6 ай бұрын
can you do this using recurssion
@user-xf3li1lk7l
11 ай бұрын
can any one explain the time complexity of it
@greatsunday4780
Жыл бұрын
It is so difficult to put Sting and Character in the same stack.
@greatsunday4780
Жыл бұрын
in java
@vaidehidharkar3348
2 жыл бұрын
Can someone compare iterative solution vs recursive solution, in terms of time complexity and suggest which one is better approach?
@dadisuperman3472
2 жыл бұрын
Same thing. No difference
@sellygobeze7173
Жыл бұрын
🐐
@ChinmayAnaokar-xm4ci
Жыл бұрын
C# code for above logic : public static class AppHelper { public static String DecodeString(String s) { Stack st = new Stack(); for (int i = 0; i < s.Length; i++) { if (s[i] != ']') { st.Push(s[i]); } else { string curr_str = ""; while (st.Peek() != '[') { curr_str = st.Peek() + curr_str; st.Pop(); } st.Pop(); string number = ""; while (st.Count > 0 && Char.IsDigit(st.Peek())) { number = st.Peek() + number; st.Pop(); } int noKTimes = Convert.ToInt32(number); while (noKTimes > 0) { for (int p = 0; p < curr_str.Length; p++) { st.Push(curr_str[p]); } noKTimes--; } } } s = ""; while (st.Count > 0) { s = st.Peek() + s; st.Pop(); } return s; } }
@kalyanking1080
3 жыл бұрын
Need recursive solution
@CostaKazistov
2 жыл бұрын
Recursive solution would be easier to code up, yes. But the above solution would be preferred in an interview setting.
@hoyinli7462
2 жыл бұрын
support
@himanshuchauhan940
2 жыл бұрын
can anyone help me in solving it in recursively
@Antinormanisto
6 ай бұрын
i don't understand why does it work
@omkarbhale442
Жыл бұрын
Instead of concatenating to string, I appended them all to a list, and called list.reverse() 😅😅 p.s. Stop scrolling comments, and solve some probolems.
@ankitkaushal442
3 жыл бұрын
wow
@RishirajDesigns
Жыл бұрын
every time he said "IN PYTHON", I was looking at my Java code, it was like speaking to me: What? don't look at me like that, go and search on google.
Пікірлер: 107