The IP Address Decomposition Problem - Compute All Valid IP Addresses From Raw IP String @BackToBackSWE
The IP Address Decomposition Problem - Compute All Valid IP Addresses From Raw IP String  @BackToBackSWE
Uploaded December 2018 | Updated November 2026, 3 hours ago
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: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww

Tuschar Roy: youtube.com/user/tusharroy2525

GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ

Jarvis Johnson: youtube.com/user/VSympathyV

Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw

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

This is problem 7.10 in the book Elements of Programming Interviews by Adnan Aziz
The IP Address Decomposition Problem - Compute All Valid IP Addresses From Raw IP StringDijkstras Algorithm vs Prims AlgorithmTest If A Binary Tree Is Height Balanced (Balanced Binary Tree on LeetCode)Deeply Understanding Logarithms In Time Complexities & Their Role In Computer ScienceEdit Distance Between 2 Strings - The Levenshtein Distance (Edit Distance on LeetCode)The Recursive Staircase - Top Down & Bottom Up Dynamic Programming (Climbing Stairs on LeetCode)Find The Second Largest Item - Heap & Tracking Approach (Beginner Big N Interview Question)How To Reverse A Singly Linked List | The Ultimate Explanation (Iteratively & Recursively)Clone A Linked List (With Random Pointers) - Linear Space Solution & Tricky Constant Space SolutionTotal Occurrences Of K In A Sorted Array (Facebook Software Engineering Interview Question)Implement An LRU Cache - The LRU Cache Eviction Policy (LRU Cache on LeetCode)Depth First & Breadth First Graph Search - DFS & BFS Graph Searching Algorithms
Back To Back SWE |

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

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER