We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

# Road Maintenance

# Road Maintenance

#### Sort by

recency

#### |

#### 7 Discussions

#### |

Please Login in order to post a comment

Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Road Maintenance Problem Solution

Here is Road Maintenance problem solution- https://programs.programmingoneonone.com/2021/07/hackerrank-road-maintenance-problem-solution.htmlThe following algorithm should work in O(N) complexity. When the road link count is 10000 then the total number of roads is n/2*(n-1) = 49995000. Lets say the road numbers run from 1-49995000 or to n/2*(n-1) . Start navigating the road links. Letâ€™s say there is a link 1-2. Assign this link the next available road number, which is one in this case. So the road lookup will get the following entries 1-(1,2) and reverse. Also the road ending in a node DS will have the following entries 1-null, 2-(1).

Letâ€™s process link 2-3 this will add one more road, road #2. Now road look up has 2 entries, 1-(1,2), 2-(2,3). The road ending in a node DS will have the following entries 1-null, 2-(1), 3-(2). Since the start of this link node 2 has an entry in road ending in a node DS, so road 1 will be joined with road 2 to form a new road #3. Now road lookup has one more entry 3-(1,3). Also since this road ends in road #3 the corresponding entry in road ending in a node DS is updates to 3-(2,3). Also the road parts DS will have one entry now, 3-(1,2). This DS stores a link for all the single road parts for this road. The entry for road 2 in road ending in a node DS will also get updated 2-(1,2)

We introduce one more DS here, road grouping. This DS will store the list of all the road with which the given road has at-least one common road, and hence are connected. At this point the DS will have the following entries. 1-(3), 2-(3), 3-(1,2). As you can see the entries in this DS are symmetrical. What this means that road #1 can be paired with 2. So one one pair of disconnected road is possible among the three roads. Lets process link 2-4. This will add one more road road #3. Now road look up has fourth entry 4-(2,4). The road ending in a node DS has one more entry 4-(4). Since the start of this road road #2 has an entry in this DS which point to 2 roads ending in #2 i.e road #1,2. These first roads will combine with road 4 and form a new road, road #5. The road look up will have the new entries as 5-(1,4) and 6-(3,4). The road parts DS will have a new entry for 5-(1,4). The road grouping will be updated with a blank entry for 4-null. The entry for 5 will be 5-(1,3,4), the following entries will be updated to 1-(3,5), 3-(1,2,5),4-(5).

The second road will combine with 4 to form road #6. The road look up will have the new entry as 6-(3,4). The entry for 6 in road parts will be 6-(2,4). The entry for 6 in road grouping will be 6-(2,3,4,5), the following entries will be updated to 2-(3,6), 3-(1,2,5, 6), 4-(5, 6), 5-(1,3,4,6)

Following will be the entries in road grouping 1-(3,5), 2-(3,6), 3-(1,2,5,6),4-(5,6),5-(1,3,4,6), (2,3,4,5). So from single road entries of 3, 2 can be selected in 3 ways. Road 3 can paired with 4. Road 5 can be paired with 2. Road 6 can be paired with with road 1. So a total of 6 possibilities.

The problem is not clear. Can you please reword or elaborate?