Table Of Contents: (I'm literally screaming. I'm sorry I'm talking so loud/fast/aggressively. I messed this up for many of my first videos. This is a past version of me.) Problem Introduction 0:00 - 1:46 Explaining The Approaches 1:46 - 6:07 The Code 6:07 - 11:07 Time & Space Complexity 11:07 - 12:47 Wrap Up 12:47 - 13:25
@@BackToBackSWE Similarly the time Complexity should also be constant? because the length of the IP address would be constant and the program would always take constant time to run.
Really really appreciate the hard work that you put into each of your videos Man !! I have a request , can you please discuss the question 'Split Array With Same Average' (LC 805)
Wow, I was struggling with backtracking till now, but this one video cleared so many concepts. Just did like 5 backtracking problems back to back after watching it. Thank you so much for such amazing content!
Similarly the time Complexity should also be constant? because the length of the IP address would be constant and the program would always take constant time to run.
I like your videos. I watch full version of ads to support you. Haha! Also, could you please past links in the description/comment area for any materials you recommended in your video? That would be awesome!
This made backtracking problems so much easier. Thank you. And it's okay you spoke loudly/aggressively. I think the passion adds emphasis to what you're teaching. Goodluck on your journey! I'm definitely subscribing.
Do you think the time Complexity should be constant? because the length of the IP address would be constant and the program would always take constant time to run.
at each point we have maximum 3 choices. if we use base case: if(segment>4) return; the maximum height of tree will be 4. so, to be exact time complexity would be: O(3^4) am i right?
Your explaining is just crystal clear! I wasn't sure why solutions on LC were checking for end of input string in base case but you explained it clearly. And in my solution, I was validating the constrain in the base case. But, I think validating it before going down a path is lot efficient. Thanks for your hard work of explaining!
I got it working in Leetcode after making few modifications to the above code class Solution { public List restoreIpAddresses(String s) { if(s.length()
Ah, yeah, all we are doing there is "clearing" the segment when we backtrack away from the choice we made. I can go more in depth if you'd like but try imagining how the recursion would pan out.
Back To Back SWE Hmm.. so it is okay if we "clear" the segment by other value than -1, isn't it? But, since without "clearing" it still output the same answer, how is it then?
It doesn't matter if you clear the path since the result is reaped ONLY when the recursion bottoms out. I should edit the code sample...I realized this a while back and forgot to edit it. You know what I mean though right? If I backtrack and keep making choices...the segment's value will get overwritten by any subsequent choices and the final result will be reaped only when we get down into the base case....then we backtrack...and keep going until the recursion finishes.
It's for checking if the current segment has leading 0, to make it clearer, python syntax: if int(segment) > 255 or (seg_len >= 2 and segment[0] == '0'): break
just clarification : the line should be if(val>255 || len>1 && snap.charAt(0)=='0') return ; AND NOT if(val>255 || len>1 && s.charAt(0)=='0') return ; 's' should be 'snap'
@@BackToBackSWE Just want to say, I had my onsite interview with Google today and got a backtracking question! I followed and explained the approach you give and pretty sure that got me a few brownie points, so thank you for passing on your knowledge once again :)
WOOO! Ok back. But all jokes aside yeah I will try to make a video on calculating recursion trees for recursive algorithms (although you'd never do this in an interview).
@@BackToBackSWE Thanks alot , It's very helpful to everyone ,if you explains the code with the Recursion Tree ,So that everyone can visualise what's going on . Your video is really very helpful . Thanks mate :) :)
The unchoose step is so that we undo the state that we added ourselves to return to the previous condition we were in before we made a choice and recursed on it.
@@BackToBackSWE Thanks! Why doesn't "-1" appear among results, if you add it? I solved this problem with a list in place of your array: bit.ly/2weiKSZ, but it took a little bit guessing when it comes to the "unchoose" step. I wonder whether we can somehow eliminate the segment variable...
@@grzegorzgorkiewicz2918 Regarding choosing and un-choosing: In graph world, when you decide to do a DFS on a node (say X), you mark it as visited in case the traversal comes back to the same node, you know that you have visited it for this recursion stack and should not include it. Now when you are done exploring all the options, you come back from the recursion stack to the X node, you can move on to next node, say node Y and perform the same DFS exploration. But before that, you need to un-choose the node X since it will be a valid candidate for the new DFS exploration that starts at Y. Now apply the same thinking here for segments and see if it helps with the understanding? And you are correct, we can choose the remove the segment variable in the un-choosing portion all together. Instead we can do currentNumbers.remove(currentNumbers.size() - 1); and it will still work. All we need to do is remove the last segment that was added to the currentNumbers from the DFS exploration to make space for the next candidateInteger in its place for the same segment. Hope I did not confuse you and this helps.
Overall, great explaination! But i am confused about one thing. when you to " res.add(path[0] +"."+path[1] +"."+path[2] +"."+path[3]);" isn't path[0] a int? and res is a list of string?
Table Of Contents: (I'm literally screaming. I'm sorry I'm talking so loud/fast/aggressively. I messed this up for many of my first videos. This is a past version of me.)
Problem Introduction 0:00 - 1:46
Explaining The Approaches 1:46 - 6:07
The Code 6:07 - 11:07
Time & Space Complexity 11:07 - 12:47
Wrap Up 12:47 - 13:25
Question : Why is the space complexity constant? There must be O(n) call stacks for n length string, no? Please, please correct me if I am wrong.
IP address has a constant max length
@@BackToBackSWE Similarly the time Complexity should also be constant? because the length of the IP address would be constant and the program would always take constant time to run.
Can you please tell why you use path[segment] = -1 at last?
@@hk123y Actually it's usually done for backtracking, which is of no use in this case.
wish you made these videos 3 years earlier .. this is priceless material for newbies. Take note .
*eye emoji*
Really really appreciate the hard work that you put into each of your videos Man !! I have a request , can you please discuss the question 'Split Array With Same Average' (LC 805)
yes
Wow, I was struggling with backtracking till now, but this one video cleared so many concepts. Just did like 5 backtracking problems back to back after watching it. Thank you so much for such amazing content!
great to hear. and nice. sure
your energy comes out of my desktop screen
lol
A minor mistake is that value could be between 0 and 255, not 1 and 255.
why it's so simple but still confusing!!!
Similarly the time Complexity should also be constant? because the length of the IP address would be constant and the program would always take constant time to run.
I like your videos. I watch full version of ads to support you. Haha! Also, could you please past links in the description/comment area for any materials you recommended in your video? That would be awesome!
hahahahahahahaha. you are cool.
One of the best solution this is! Thanks a lot!
Is there a code available for this anywhere?
almost: github.com/bephrem1/backtobackswe/issues/1
Very great explanation. I was looking for a way to remember these patterns. Keep doing more and more videos like this.
ye
Thanks for such a wonderful explaination
Dude, I know you are the best. Please just don't shout at me. You do this in every video but still, you are the best with 3 keys.
old video lol
This made backtracking problems so much easier. Thank you. And it's okay you spoke loudly/aggressively. I think the passion adds emphasis to what you're teaching.
Goodluck on your journey! I'm definitely subscribing.
Wow, this is an amazing video! Thank you for explaining this so thoroughly! Love the enthusiasm too 👊🏽👊🏽
thx
Do you think the time Complexity should be constant? because the length of the IP address would be constant and the program would always take constant time to run.
Love how enthusiastic you are, you don't find that with a lot of tutors. Preparing for a coding interview, thanks for the help!
Sir if we use recursion not backtracking then the time complexity will remain same or it will be effected?????
man, your thinking process is gold
haha thx
at each point we have maximum 3 choices.
if we use base case: if(segment>4) return;
the maximum height of tree will be 4.
so, to be exact time complexity would be: O(3^4)
am i right?
Yes, we have a constant amount of calls at max asymptotically.
@@BackToBackSWE thanx man!
@@heyitsnikhil7956 sure
Thank you so much for your enthusiasm; it helps me to learn faster!
Your explaining is just crystal clear! I wasn't sure why solutions on LC were checking for end of input string in base case but you explained it clearly. And in my solution, I was validating the constrain in the base case. But, I think validating it before going down a path is lot efficient. Thanks for your hard work of explaining!
Nice
You just killed it ,So much energy :) just loved it .I got the whole concept very clearly.
Thanks
great
did u try running your code? Does it pass in leetcode? I couldnt get it to give me the right solution
hmm
I had similar kind of logic, leetcode has got some crazy cases, which didn't even make sense for me.
I got it working in Leetcode after making few modifications to the above code
class Solution {
public List restoreIpAddresses(String s) {
if(s.length()
Nice solution! It would be very kind of you to talk a little slower. Thanks again
love
Yup sometimes i had to reduce the speed to 0.5
@@zengamingu hey, ok
This man spits GOLD
nah
I think that it should not be break,but continue on if for constrains.
Generally awesome video bro
thx
Time complexity is O(1) 🤔😦
I like your Energy and teaching style, please make more videos.
ok
Wow! I've always struggled in implementing backtracking, but this video explains it best!
Love the explanation. You just made the question so easy to code
great
Please use pictorial diagram instead of just speaking.
Noted.
can you please share github link in the description
There is no code sample for this currently I think
Hi Ben, seems u forgot to explain the "unchoose" ("our choice") part.
Could u please tell us more? (path[segment] = -1)
Ah, yeah, all we are doing there is "clearing" the segment when we backtrack away from the choice we made. I can go more in depth if you'd like but try imagining how the recursion would pan out.
Back To Back SWE Hmm.. so it is okay if we "clear" the segment by other value than -1, isn't it? But, since without "clearing" it still output the same answer, how is it then?
It doesn't matter if you clear the path since the result is reaped ONLY when the recursion bottoms out. I should edit the code sample...I realized this a while back and forgot to edit it. You know what I mean though right? If I backtrack and keep making choices...the segment's value will get overwritten by any subsequent choices and the final result will be reaped only when we get down into the base case....then we backtrack...and keep going until the recursion finishes.
Back To Back SWE Yap.. I got it, Ben.. in all, thanks for being so helpful! Keep up the good work 👏🏻
@@hizkiajuan sure
why should len>=2 in order to break plzz help
I don't remember the code but it has something to do with validation right? Validating a segment
It's for checking if the current segment has leading 0, to make it clearer, python syntax:
if int(segment) > 255 or (seg_len >= 2 and segment[0] == '0'):
break
just clarification :
the line should be
if(val>255 || len>1 && snap.charAt(0)=='0')
return ;
AND NOT
if(val>255 || len>1 && s.charAt(0)=='0')
return ;
's' should be 'snap'
ok cant verify replying fast to comments
Thank you for all your videos, they've been a great resource for me and I think I'm finally starting to get backtracking down!
That is pretty cool haha. I made all these backtracking vids while I was still getting the hang of making videos so they're rough...
@@BackToBackSWE Just want to say, I had my onsite interview with Google today and got a backtracking question! I followed and explained the approach you give and pretty sure that got me a few brownie points, so thank you for passing on your knowledge once again :)
@@andrewghorbani5991 fuego. go get em'
@@BackToBackSWE 2 years later I find myself back here haha! Your vids are a gem my dude
you saved me from Output Limit Exceeded
great presentation, thank you my Brother
yes
Now you know how to solve backtracking problems and how to scratch your itch while making a youtube video...
nice
you da man Ben
hey
Can you please generate a tree and show how backtracking is working here .
Yeah, I'll run back in time and edit that in, brb 🏃🏃💨🏃🏃💨
WOOO! Ok back. But all jokes aside yeah I will try to make a video on calculating recursion trees for recursive algorithms (although you'd never do this in an interview).
@@BackToBackSWE Thanks alot , It's very helpful to everyone ,if you explains the code with the Recursion Tree ,So that everyone can visualise what's going on . Your video is really very helpful . Thanks mate :) :)
@@amitranjan6998 sure
What is meant here with the unchoose step? Why is it important?
The unchoose step is so that we undo the state that we added ourselves to return to the previous condition we were in before we made a choice and recursed on it.
@@BackToBackSWE Thanks! Why doesn't "-1" appear among results, if you add it? I solved this problem with a list in place of your array: bit.ly/2weiKSZ, but it took a little bit guessing when it comes to the "unchoose" step. I wonder whether we can somehow eliminate the segment variable...
@@grzegorzgorkiewicz2918 Regarding choosing and un-choosing: In graph world, when you decide to do a DFS on a node (say X), you mark it as visited in case the traversal comes back to the same node, you know that you have visited it for this recursion stack and should not include it. Now when you are done exploring all the options, you come back from the recursion stack to the X node, you can move on to next node, say node Y and perform the same DFS exploration. But before that, you need to un-choose the node X since it will be a valid candidate for the new DFS exploration that starts at Y.
Now apply the same thinking here for segments and see if it helps with the understanding?
And you are correct, we can choose the remove the segment variable in the un-choosing portion all together. Instead we can do currentNumbers.remove(currentNumbers.size() - 1); and it will still work. All we need to do is remove the last segment that was added to the currentNumbers from the DFS exploration to make space for the next candidateInteger in its place for the same segment.
Hope I did not confuse you and this helps.
Love the Energy.
Thanks
sure
Perfect
sorta
Thank you! :)
Overall, great explaination! But i am confused about one thing. when you to " res.add(path[0] +"."+path[1] +"."+path[2] +"."+path[3]);" isn't path[0] a int? and res is a list of string?
it is a string
@@BackToBackSWE But path is a int[ ] as how you defined it.
Good observation! However, when you concatenate the ints (path[0], path[1], ...) with the period ("."), they become strings. Do you see it now?