Airport Connections

Category: Graphs

```

Problem Statement

["ORD", "BGI"], ["BGI", "LGA"], ["SIN", "CDG"], ["CDG", "SIN"], ["CDG", "BUD"], ["DEL", "DOH"], ["DEL", "CDG"], ["TLV", "DEL"], ["EWR", "HND"], ["HND", "ICN"], ["HND", "JFK"], ["ICN", "JFK"], ["JFK", "LGA"], ["EYW", "LHR"], ["LHR", "SFO"], ["SFO", "SAN"], ["SFO", "DSM"], ["SAN", "EYW"], ] startingAirport = "LGA" Sample Output // ["LGA", "TLV"], ["LGA", "SFO"], and ["LGA", "EWR"] Hints Hint 1 Start by creating a graph out of the inputs. Each airport should be a vertex in the graph, and each route should be an edge. The graph should be directed with potential cycles, since it's possible for there to be round-trip ights between airports or for some series of ights to eventually lead back to an arbitrary starting point. How can this graph be useful? Hint 2 Using the graph mentioned in Hint #1, try getting all of the airports that are unreachable from the starting airport. This can be done using depth-rst search. Is the number of unreachable airports the answer? If not, what extra information do you need to get to the answer? Hint 3 A single unreachable airport could have connections to a bunch of other unreachable airports, potentially making it more "valuable", since adding one connection to it would make many other airports reachable. Hint 4 Calculate the number of unreachable airports that are reachable from each unreachable airport (this can be done using depth-rst search), sort them in descending order according to this number, and count the minimum number of connections that need to be added by iterating through this sorted list of unreachable airports, removing every unreachable airport's unreachable connections as you go through the list. Optimal Space & Time Complexity O(a * (a + r) + a + r + alog(a)) time | O(a + r) space - where a is the number of airports and r is the number of routes

```

Approach & Solution

Solution 1

``` public static int airportConnections( List airports, List> routes, String startingAirport) { Map airportGraph = createAirportGraph(airports, routes); List unreachableAirportNodes = getUnreachableAirportNodes(airportGraph, airports, startingAirport); markUnreachableConnections(airportGraph, unreachableAirportNodes); return getMinNumberOfNewConnections(airportGraph, unreachableAirportNodes); } // O(a + r) time | O(a + r) space public static Map createAirportGraph( List airports, List> routes) { Map airportGraph = new HashMap(); for (String airport : airports) { airportGraph.put(airport, new AirportNode(airport)); } for (List route : routes) { String airport = route.get(0); String connection = route.get(1); airportGraph.get(airport).connections.add(connection); } return airportGraph; } // O(a + r) time | O(a) space public static List getUnreachableAirportNodes( Map airportGraph, List airports, String startingAirport) { Set visitedAirports = new HashSet(); depthFirstTraverseAirports(airportGraph, startingAirport, visitedAirports); List unreachableAirportNodes = new ArrayList(); for (String airport : airports) { if (visitedAirports.contains(airport)) continue; AirportNode airportNode = airportGraph.get(airport); airportNode.isReachable = false; unreachableAirportNodes.add(airportNode); } return unreachableAirportNodes; } public static void depthFirstTraverseAirports( Map airportGraph, String airport, Set visitedAirports) { if (visitedAirports.contains(airport)) return; visitedAirports.add(airport); List connections = airportGraph.get(airport).connections; for (String connection : connections) { depthFirstTraverseAirports(airportGraph, connection, visitedAirports); } } // i | // O(a * (a + r)) time | O(a) space public static void markUnreachableConnections( Map airportGraph, List unreachableAirportNodes) {

Solution 2

``` 70 } 71 72 public static void depthFirstAddUnreachableConnections( 73 Map airportGraph, 74 String airport, 75 List unreachableConnections, 76 Set visitedAirports) { 77 if (airportGraph.get(airport).isReachable) return; 78 if (visitedAirports.contains(airport)) return; 79 visitedAirports.add(airport); 80 unreachableConnections.add(airport); 81 List connections = airportGraph.get(airport).connections; 82 for (String connection : connections) { 83 depthFirstAddUnreachableConnections( 84 airportGraph, connection, unreachableConnections, visitedAirports); 85 } 86 } 87 88 // O(alog(a) + a + r) time | O(1) space 89 public static int getMinNumberOfNewConnections( 90 Map airportGraph, List unreachableAirportNodes) { 91 unreachableAirportNodes.sort( 92 (a1, a2) -> a2.unreachableConnections.size() - a1.unreachableConnections.size()); 93 int numberOfNewConnections = 0; 94 for (AirportNode airportNode : unreachableAirportNodes) { 95 if (airportNode.isReachable) continue; 96 numberOfNewConnections++; 97 for (String connection : airportNode.unreachableConnections) { 98 airportGraph.get(connection).isReachable = true; 99 } 100 } 101 return numberOfNewConnections; 102 } 103 104 static class AirportNode { 105 String airport; 106 List connections; 107 boolean isReachable; 108 List unreachableConnections; 109 110 public AirportNode(String airport) { 111 this.airport = airport; 112 connections = new ArrayList(); 113 isReachable = true; 114 unreachableConnections = new ArrayList(); 115 } 116 } 117 } 118

Solution 3

```java import java.util.*; class Program { // O(a * (a + r) + a + r + alog(a)) time | O(a + r) space - where a is the number of airports and // r is the number of routes public static int airportConnections( List airports, List> routes, String startingAirport) { Map airportGraph = createAirportGraph(airports, routes); List unreachableAirportNodes = getUnreachableAirportNodes(airportGraph, airports, startingAirport); markUnreachableConnections(airportGraph, unreachableAirportNodes); return getMinNumberOfNewConnections(airportGraph, unreachableAirportNodes); } // O(a + r) time | O(a + r) space public static Map createAirportGraph( List airports, List> routes) { Map airportGraph = new HashMap(); for (String airport : airports) { airportGraph.put(airport, new AirportNode(airport)); } for (List route : routes) { String airport = route.get(0); String connection = route.get(1); airportGraph.get(airport).connections.add(connection); } return airportGraph; } // O(a + r) time | O(a) space public static List getUnreachableAirportNodes( Map airportGraph, List airports, String startingAirport) { Set visitedAirports = new HashSet(); depthFirstTraverseAirports(airportGraph, startingAirport, visitedAirports); List unreachableAirportNodes = new ArrayList(); for (String airport : airports) { if (visitedAirports.contains(airport)) continue; AirportNode airportNode = airportGraph.get(airport); airportNode.isReachable = false; unreachableAirportNodes.add(airportNode); } return unreachableAirportNodes; } public static void depthFirstTraverseAirports( Map airportGraph, String airport, Set visitedAirports) { if (visitedAirports.contains(airport)) return; visitedAirports.add(airport); List connections = airportGraph.get(airport).connections; for (String connection : connections) { depthFirstTraverseAirports(airportGraph, connection, visitedAirports); }

```

Test Cases

``` Test Case 1 { "airports": [ "BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA", "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD" ], "routes": [ ["DSM", "ORD"], ["ORD", "BGI"], ["BGI", "LGA"], ["SIN", "CDG"], ["CDG", "SIN"], ["CDG", "BUD"], ["DEL", "DOH"], ["DEL", "CDG"], ["TLV", "DEL"], ["EWR", "HND"], ["HND", "ICN"], ["HND", "JFK"], ["ICN", "JFK"], ["JFK", "LGA"], ["EYW", "LHR"], ["LHR", "SFO"], ["SFO", "SAN"], ["SFO", "DSM"], ["SAN", "EYW"] ], "startingAirport": "LGA" } Test Case 2 { "airports": [ "BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA", "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD" ], "routes": [], "startingAirport": "LGA" } Test Case 3 { "airports": [ "BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA", "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD" ], "routes": [["LGA", "DSM"], ["LGA", "ORD"], ["LGA", "EYW"]], "startingAirport": "LGA" } Test Case 4 { "airports": [ "BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA", "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD" ], "routes": [ ["LGA", "DSM"], ["DSM", "ORD"], ["LGA", "EYW"], ["EYW", "JFK"], ["EYW", "EWR"], ["JFK", "ICN"] ], "startingAirport": "LGA" } Test Case 5 { "airports": [ "BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA", "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD" ], "routes": [ ["LGA", "DSM"], ["DSM", "ORD"], ["LGA", "EYW"], ["EYW", "JFK"], ["EYW", "EWR"], ["JFK", "ICN"], ["LGA", "ICN"], ["ICN", "ORD"], ["ICN", "EWR"], ["JFK", "DSM"] ], "startingAirport": "LGA" } Test Case 6 { "airports": [ "BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA", "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD" ], "routes": [ ["LGA", "DSM"], ["DSM", "ORD"], ["LGA", "EYW"], ["EYW", "JFK"], ["EYW", "EWR"], ["JFK", "ICN"], ["LGA", "ICN"], ["ICN", "ORD"], ["ICN", "EWR"], ["JFK", "DSM"], ["ICN", "JFK"], ["ORD", "DSM"], ["DSM", "LGA"], ["JFK", "LGA"], ["JFK", "HND"] ], "startingAirport": "LGA" } Test Case 7 { "airports": [ "BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA", "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD" ], "routes": [ ["LGA", "DSM"], ["DSM", "ORD"], ["LGA", "EYW"], ["EYW", "JFK"], ["EYW", "EWR"], ["JFK", "ICN"], ["LGA", "ICN"], ["ICN", "ORD"], ["ICN", "EWR"], ["JFK", "DSM"], ["ICN", "JFK"], ["ORD", "DSM"], ["DSM", "LGA"], ["JFK", "LGA"], ["JFK", "HND"], ["SFO", "SIN"], ["SFO", "CDG"], ["SFO", "LHR"], ["LHR", "DEL"], ["DEL", "BGI"], ["DEL", "DOH"], ["DOH", "SAN"] ], "startingAirport": "LGA" } Test Case 8 { "airports": [ "BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA", "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD" ], "routes": [ ["LGA", "DSM"], ["DSM", "ORD"], ["EYW", "JFK"], ["EYW", "EWR"], ["JFK", "ICN"], ["LGA", "ICN"], ["ICN", "ORD"], ["ICN", "EWR"], ["JFK", "DSM"], ["ICN", "JFK"], ["ORD", "DSM"], ["DSM", "LGA"], ["JFK", "LGA"], ["JFK", "HND"], ["SFO", "SIN"], ["SFO", "CDG"], ["SFO", "LHR"], ["LHR", "DEL"], ["DEL", "BGI"], ["DEL", "DOH"], ["DOH", "SAN"] ], "startingAirport": "LGA" } Test Case 9 { "airports": [ "BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA", "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD" ], "routes": [ ["LGA", "DSM"], ["SIN", "BGI"], ["SIN", "CDG"], ["SIN", "DEL"], ["SIN", "DOH"], ["SIN", "DSM"], ["SIN", "EWR"], ["SIN", "EYW"], ["SIN", "HND"], ["SIN", "ICN"], ["SIN", "JFK"], ["SIN", "LHR"], ["SIN", "ORD"], ["SFO", "SIN"], ["SFO", "SAN"] ], "startingAirport": "LGA" } Test Case 10 { "airports": [ "BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA", "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD" ], "routes": [ ["LGA", "DSM"], ["DSM", "ORD"], ["SIN", "BGI"], ["SIN", "CDG"], ["CDG", "DEL"], ["DEL", "DOH"], ["DEL", "CDG"], ["DEL", "EWR"], ["HND", "ICN"], ["ICN", "JFK"], ["JFK", "LGA"], ["JFK", "SFO"], ["EYW", "LHR"], ["SFO", "ORD"], ["SFO", "LGA"] ], "startingAirport": "LGA" } Test Case 11 { "airports": [ "BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA", "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD" ], "routes": [ ["LGA", "DSM"], ["DSM", "ORD"], ["SIN", "BGI"], ["SIN", "CDG"], ["CDG", "DEL"], ["DEL", "DOH"], ["DEL", "CDG"], ["DEL", "EWR"], ["HND", "ICN"], ["ICN", "JFK"], ["JFK", "LGA"], ["JFK", "SFO"], ["EYW", "LHR"], ["SFO", "ORD"], ["SFO", "LGA"], ["SFO", "SIN"], ["CDG", "EYW"], ["LGA", "SAN"] ], "startingAirport": "LGA" } Test Case 12 { "airports": [ "BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA", "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD" ], "routes": [ ["LGA", "DSM"], ["DSM", "ORD"], ["SIN", "BGI"], ["SIN", "CDG"], ["CDG", "DEL"], ["DEL", "DOH"], ["DEL", "CDG"], ["DEL", "EWR"], ["HND", "ICN"], ["ICN", "JFK"], ["JFK", "LGA"], ["JFK", "SFO"], ["EYW", "LHR"], ["SFO", "ORD"], ["SFO", "LGA"], ["SFO", "SIN"], ["CDG", "EYW"], ["ORD", "HND"], ["HND", "SAN"], ["LGA", "TLV"], ["LGA", "BUD"] ], "startingAirport": "LGA" } Test Case 13 { "airports": [ "BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA", "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD" ], "routes": [ ["DSM", "ORD"], ["ORD", "BGI"], ["BGI", "LGA"], ["SIN", "CDG"], ["CDG", "DEL"], ["DEL", "DOH"], ["DOH", "SIN"], ["EWR", "HND"], ["HND", "ICN"], ["ICN", "JFK"], ["JFK", "LGA"], ["EYW", "LHR"], ["LHR", "SFO"], ["SFO", "SAN"], ["SAN", "EYW"] ], "startingAirport": "LGA" } Test Case 14 { "airports": [ "BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA", "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD" ], "routes": [ ["DSM", "ORD"], ["ORD", "BGI"], ["BGI", "LGA"], ["SIN", "CDG"], ["CDG", "DEL"], ["DEL", "DOH"], ["DOH", "SIN"], ["EWR", "HND"], ["HND", "ICN"], ["ICN", "JFK"], ["JFK", "LGA"], ["EYW", "LHR"], ["LHR", "SFO"], ["SFO", "SAN"], ["SFO", "ORD"], ["SAN", "EYW"] ], "startingAirport": "LGA" } Test Case 15 { "airports": [ "BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA", "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD" ], "routes": [ ["DSM", "ORD"], ["ORD", "BGI"], ["BGI", "LGA"], ["SIN", "CDG"], ["CDG", "DEL"], ["DEL", "DOH"], ["DOH", "SIN"], ["EWR", "HND"], ["HND", "ICN"], ["ICN", "JFK"], ["JFK", "LGA"], ["EYW", "LHR"], ["LHR", "SFO"], ["SFO", "SAN"], ["SFO", "DSM"], ["SAN", "EYW"] ], "startingAirport": "LGA" }