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

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

++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++++++++++++++++++++++++++++++++++

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

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

[gourabchowdhury]

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

[sammiewalker]

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

[sarahzaman]

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.

[SudhanshuKumar-lpnr]

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.

[abhinavnarang]

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.

[surajch]

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

[patilganesh]

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

[see]

Thanks for such a wonderful explaination

[shashankkumarshankar]

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!

[THEAVISTER]

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

[xwa]

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!

[heyitsnikhil]

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?

[nikkis]

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

[hizkiajuan]

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

[yashadukia]

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

[janvisingla]

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

[bhavyachawla]

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)

[taksh]

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