The IP Address Decomposition Problem - Compute All Valid IP Addresses From Raw IP String

Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: You are given a raw IP address string without period separators between the digits. Return all valid IP addresses that can be created from the raw IP string where it is your job to place the periods.
This is sort of a knowledge question but if you get this in an interview you'd probably get the constraints, otherwise, it is the interviewer's fault for being a bad interviewer since general SWE questions should primarily be about problem solving skills and not domain specific knowledge/facts.
Whenever we hear "compute" or "generate" we know that we will have to do some sort of repeated looping or recursion in a backtracking approach. For this problem, we can do either.
Approach 1 (iteration)
A triple nested set of for loops where in each section we create a part of the IP string, validate that section we just snipped out and then continue on to generate the rest of the IP string
Approach 2 (backtracking)
The 3 Keys To Backtracking:
Our Choice:
- We will take snippets of substrings 1-3 characters long
Our Constraints:
- We cannot have a value greater than 255 or less than 0 in any subsection.
- We cannot have a leading 0 in any subsection
Our Goal:
- Get 4 valid subsections out of the raw string that we started with that will comprise the fully valid IP recomposition
We can make progress through the string, slowly decoding it in all ways possible by taking a snippet, validating it, and then continuing on in the generation path.
Since we will be using recursion, each recursive call will express all possible ways to arrange a certain subsection of the string that is...
Until we reach the base case which is when we have all 4 segments filled out (and by default, our index pointer has progressed to the string's length).
Complexities
Time: O(1)
- Off the bat, we know that we will have a constant time complexity because there are a limited amount of IP addresses (2^32 to be exact) so our time complexity will fall as O(1) ("constant")
Space: O(1)
- By the same line of reasoning, our space complexity is O(1)
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This is problem 7.10 in the book Elements of Programming Interviews by Adnan Aziz

[@BackToBackSWE]

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

[@algorithmimplementer415]

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.

[@BackToBackSWE]

IP address has a constant max length

[@SudhanshuKumar-lp1nr]

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

[@hk123y]

Can you please tell why you use path[segment] = -1 at last?

[@SudhanshuKumar-lp1nr]

@@hk123y Actually it's usually done for backtracking, which is of no use in this case.

[@sarahzaman3173]

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.

[@sammiewalker2860]

Love how enthusiastic you are, you don't find that with a lot of tutors. Preparing for a coding interview, thanks for the help!

[@AradhyaKasat]

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!

[@BackToBackSWE]

great to hear. and nice. sure

[@surajch2678]

Very great explanation. I was looking for a way to remember these patterns. Keep doing more and more videos like this.

[@BackToBackSWE]

ye

[@gourabchowdhury6456]

wish you made these videos 3 years earlier .. this is priceless material for newbies. Take note .

[@BackToBackSWE]

*eye emoji*

[@janvisingla3746]

You just killed it ,So much energy :) just loved it .I got the whole concept very clearly. Thanks

[@BackToBackSWE]

great

[@nikkis8102]

Thank you so much for your enthusiasm; it helps me to learn faster!

[@THEAVISTER]

Wow, this is an amazing video! Thank you for explaining this so thoroughly! Love the enthusiasm too 👊🏽👊🏽

[@BackToBackSWE]

thx

[@SudhanshuKumar-lp1nr]

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.

[@shashankkumarshankar3655]

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!

[@BackToBackSWE]

Nice

[@yashadukia9646]

Love the explanation. You just made the question so easy to code

[@BackToBackSWE]

great

[@kaichenghu3826]

man, your thinking process is gold

[@BackToBackSWE]

haha thx

[@see2672]

Thanks for such a wonderful explaination

[@xwa130]

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!

[@BackToBackSWE]

hahahahahahahaha. you are cool.

[@mrshubh101]

Wow! I've always struggled in implementing backtracking, but this video explains it best!

[@SudhanshuKumar-lp1nr]

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.

[@patil88ganesh]

One of the best solution this is! Thanks a lot! Is there a code available for this anywhere?

[@BackToBackSWE]

almost: github.com/bephrem1/backtobackswe/issues/1

[@bhavyachawla7176]

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)

[@BackToBackSWE]

yes

[@andrewghorbani5991]

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!

[@BackToBackSWE]

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

[@andrewghorbani5991]

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

[@BackToBackSWE]

@@andrewghorbani5991 fuego. go get em'

[@andrewghorbani5991]

@@BackToBackSWE 2 years later I find myself back here haha! Your vids are a gem my dude

[@SudhanshuKumar-lp1nr]

Love the Energy.

[@emonitani]

great presentation, thank you my Brother

[@BackToBackSWE]

yes

[@abhinavnarang7855]

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.

[@BackToBackSWE]

old video lol

[@bakhtiyardoskenov191]

Thank you! :)

[@tathagatgawle2172]

I like your Energy and teaching style, please make more videos.

[@BackToBackSWE]

ok

[@taksh8138]

Sir if we use recursion not backtracking then the time complexity will remain same or it will be effected?????

[@heyitsnikhil7956]

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?

[@BackToBackSWE]

Yes, we have a constant amount of calls at max asymptotically.

[@heyitsnikhil7956]

@@BackToBackSWE thanx man!

[@BackToBackSWE]

@@heyitsnikhil7956 sure

[@gauravsalunke9900]

This man spits GOLD

[@BackToBackSWE]

nah

[@dragoslavmilutinovic5731]

I think that it should not be break,but continue on if for constrains. Generally awesome video bro

[@BackToBackSWE]

thx

[@shikharchaudhary6984]

you saved me from Output Limit Exceeded

[@user-ru3us6rs1r]

Thanks

[@BackToBackSWE]

sure

[@novadragonxx5]

you da man Ben

[@BackToBackSWE]

hey

[@meghaharlalka]

did u try running your code? Does it pass in leetcode? I couldnt get it to give me the right solution

[@BackToBackSWE]

hmm

[@justinejose5111]

I had similar kind of logic, leetcode has got some crazy cases, which didn't even make sense for me.

[@sandeepkumarnagamalla1020]

I got it working in Leetcode after making few modifications to the above code class Solution { public List restoreIpAddresses(String s) { if(s.length()

[@hizkiajuan]

Hi Ben, seems u forgot to explain the "unchoose" ("our choice") part. Could u please tell us more? (path[segment] = -1)

[@BackToBackSWE]

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.

[@hizkiajuan]

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?

[@BackToBackSWE]

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.

[@hizkiajuan]

Back To Back SWE Yap.. I got it, Ben.. in all, thanks for being so helpful! Keep up the good work 👏🏻

[@BackToBackSWE]

@@hizkiajuan sure

[@lokeshs9449]

your energy comes out of my desktop screen

[@BackToBackSWE]

lol

[@mmfawzy4850]

Perfect

[@BackToBackSWE]

sorta

[@gordongao840]

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?

[@BackToBackSWE]

it is a string

[@gordongao840]

@@BackToBackSWE But path is a int[ ] as how you defined it.

[@kalebs.gebrekirstos8041]

Good observation! However, when you concatenate the ints (path[0], path[1], ...) with the period ("."), they become strings. Do you see it now?

[@muralijagdev]

can you please share github link in the description

[@BackToBackSWE]

There is no code sample for this currently I think

[@grzegorzgorkiewicz2918]

What is meant here with the unchoose step? Why is it important?

[@BackToBackSWE]

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.

[@grzegorzgorkiewicz2918]

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

[@viditmaniyar2846]

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

[@abhinavghosh725]

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]

ok cant verify replying fast to comments

[@parteeksachdeva3039]

why should len>=2 in order to break plzz help

[@BackToBackSWE]

I don't remember the code but it has something to do with validation right? Validating a segment

[@rieljunliguid4043]

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

[@trantung2013]

A minor mistake is that value could be between 0 and 255, not 1 and 255.

[@sophiehall38]

Nice solution! It would be very kind of you to talk a little slower. Thanks again

[@BackToBackSWE]

love

[@zengamingu]

Yup sometimes i had to reduce the speed to 0.5

[@BackToBackSWE]

@@zengamingu hey, ok

[@amitranjan6998]

Can you please generate a tree and show how backtracking is working here .

[@BackToBackSWE]

Yeah, I'll run back in time and edit that in, brb 🏃🏃💨🏃🏃💨

[@BackToBackSWE]

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

[@amitranjan6998]

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

[@BackToBackSWE]

@@amitranjan6998 sure

[@anujsrivastav6444]

why it's so simple but still confusing!!!

[@decostarkumar2562]

Time complexity is O(1) 🤔😦

[@RizwanAhmed-pv1mg]

Please use pictorial diagram instead of just speaking.

[@BackToBackSWE]

Noted.

[@ritikmishra3643]

Now you know how to solve backtracking problems and how to scratch your itch while making a youtube video...

[@BackToBackSWE]

nice