Connecting Cities With Minimum Cost

Medium

Asked by:

4 views

Topics:

Greedy AlgorithmsGraphs

There are n cities labeled from 1 to n. You are given the integer n and an array connections where connections[i] = [city1_i, city2_i, cost_i] indicates that the cost of connecting city city1_i and city city2_i together is cost_i. You should choose some connections such that the cost of connecting all the n cities is minimized.

Return the minimum cost to connect all the cities. If it is not possible to connect all the cities, return -1.

The cost of connecting all cities is the sum of the costs of the connections you use.

Example 1:

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2. The cheapest is [2,3,1] and [1,2,5] which gives a total cost of 6.

Example 2:

Input: n = 4, connections = [[1,2,3],[3,4,4]]
Output: -1
Explanation: There is no way to connect all cities even if all edges are used.

Constraints:

1 <= n <= 10⁴
1 <= connections.length <= 10⁴
connections[i].length == 3
1 <= city1_i, city2_i <= n
0 <= cost_i <= 10⁵

Connecting Cities With Minimum Cost

Medium

Asked by:

4 views

Topics:

Greedy AlgorithmsGraphs

There are n cities labeled from 1 to n. You are given the integer n and an array connections where connections[i] = [city1_i, city2_i, cost_i] indicates that the cost of connecting city city1_i and city city2_i together is cost_i. You should choose some connections such that the cost of connecting all the n cities is minimized.

Return the minimum cost to connect all the cities. If it is not possible to connect all the cities, return -1.

The cost of connecting all cities is the sum of the costs of the connections you use.

Example 1:

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2. The cheapest is [2,3,1] and [1,2,5] which gives a total cost of 6.

Example 2:

Input: n = 4, connections = [[1,2,3],[3,4,4]]
Output: -1
Explanation: There is no way to connect all cities even if all edges are used.

Constraints:

1 <= n <= 10⁴
1 <= connections.length <= 10⁴
connections[i].length == 3
1 <= city1_i, city2_i <= n
0 <= cost_i <= 10⁵

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible costs for connecting two cities, and can costs be negative?
If it's impossible to connect all cities, what value should I return?
Are there any constraints on the number of cities, or the number of possible connections given as input?
Is the input graph guaranteed to be connected, or could there be disjoint sets of cities?
If there are multiple ways to connect all cities with the same minimum cost, is any valid solution acceptable?

Brute Force Solution

Approach

The brute force approach to connecting cities with minimum cost means we explore every possible way to build roads between cities. We check the total cost for each of these possibilities. We eventually pick the cheapest option that connects all cities.

Here's how the algorithm would work step-by-step:

First, think about all the possible roads you could build between the cities. Each road has a specific cost.
Start by considering building no roads at all. This probably won't connect all the cities, but we need to check it anyway.
Next, try building only one road. Pick any road and see if that single road connects all cities. If not, move to the next possible road.
Then, try building all possible combinations of two roads. For each combination, check if it connects all cities. If not, discard it and try another combination.
Continue this process, considering all possible combinations of three roads, then four roads, and so on, until you've checked building all the roads.
For each combination of roads that *does* connect all the cities, calculate the total cost of building those roads.
Finally, compare the total costs of all the valid combinations (those that connect all cities) and choose the combination with the lowest cost. This is your solution.

Code Implementation

def connecting_cities_with_minimum_cost_brute_force(number_of_cities, roads):    minimum_cost = float('inf')
    # Iterate through all possible combinations of roads.
    for i in range(1 << len(roads)):
        roads_subset = []
        cost = 0
        for j in range(len(roads)):
            if (i >> j) & 1:
                roads_subset.append(roads[j])
                cost += roads[j][2]
        
        # Check if the subset connects all cities.
        if is_connected(number_of_cities, roads_subset):
            # Update minimum cost if necessary
            minimum_cost = min(minimum_cost, cost)
    
    if minimum_cost == float('inf'):
        return -1
    return minimum_cost

def is_connected(number_of_cities, roads_subset):
    if not roads_subset and number_of_cities > 1:
        return False

    parent = list(range(number_of_cities))

    def find(city_index):
        if parent[city_index] != city_index:
            parent[city_index] = find(parent[city_index])
        return parent[city_index]

    def union(city_index_1, city_index_2):
        root_1 = find(city_index_1)
        root_2 = find(city_index_2)
        parent[root_2] = root_1

    for city_index_1, city_index_2, _ in roads_subset:
        union(city_index_1, city_index_2)

    # Check if all cities are in the same connected component.
    root = find(0)
    for city_index in range(1, number_of_cities):
        if find(city_index) != root:
            return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^(n*n)) – The algorithm explores all possible subsets of roads between the n cities. In the worst case, every pair of cities could potentially have a road between them. The maximum number of possible roads is proportional to n*n (specifically n*(n-1)/2, the number of pairs). For each of these potential roads, we either include it or don't, meaning we have 2 choices for each road. Since there are approximately n*n possible roads, this leads to 2 raised to the power of (n*n) possibilities to consider. Each possibility needs to be evaluated to check connectivity, so the total time complexity becomes O(2^(n*n)).

Space Complexity

O(2^E) – The brute force approach explores all possible subsets of roads, where E is the number of possible roads between the cities. Each subset needs to be stored temporarily to check for connectivity and cost, leading to a maximum of 2^E subsets being considered. The space to store these subsets dominates the auxiliary space. Therefore, the auxiliary space complexity is O(2^E), where E represents the number of edges (possible roads).

Optimal Solution

Approach

The problem involves finding the least expensive way to connect a set of cities using roads. Instead of trying every possible road combination, we'll build the road network gradually, always choosing the cheapest road that connects a new city to the existing network. This avoids unnecessary roads and focuses on the most cost-effective connections.

Here's how the algorithm would work step-by-step:

Think of each city as its own separate group at the start.
Look at all the possible roads and find the very cheapest one.
Check if the two cities connected by this cheapest road are in different groups. If they are, it means connecting them adds a new city to the overall connected network.
If the cities are in different groups, build that road! Also, merge the two groups together to show that those cities are now part of the same connected network.
Repeat steps 2-4, always picking the next cheapest road that connects two groups of cities that aren't already connected.
Keep doing this until all the cities are in one big group. That means all cities are connected.
Add up the costs of all the roads you built. This gives you the minimum cost to connect all the cities.

Code Implementation

def minimum_cost_to_connect_cities(number_of_cities, roads):    parent = list(range(number_of_cities + 1))
    def find(city_node):
        if parent[city_node] != city_node:
            parent[city_node] = find(parent[city_node])
        return parent[city_node]
    def union(city_node_a, city_node_b):
        root_a = find(city_node_a)
        root_b = find(city_node_b)
        if root_a != root_b:
            parent[root_a] = root_b
            return True
        return False
    roads.sort(key=lambda road: road[2])
    minimum_cost = 0
    edges_used = 0

    # Iterate through sorted edges to find min cost
    for city_node_a, city_node_b, road_cost in roads:
        # Only connect if the cities are not already connected
        if union(city_node_a, city_node_b):

            minimum_cost += road_cost
            edges_used += 1

        # Short circuit if all nodes are connected
        if edges_used == number_of_cities - 1:
            break
    
    # Check for unconnected graph
    number_of_components = 0
    for i in range(1, number_of_cities + 1):
        if parent[i] == i:
            number_of_components += 1
    
    if number_of_components > 1:
        return -1

    return minimum_cost

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(E log E) – The algorithm's runtime is dominated by sorting the edges and the Union-Find operations. Sorting the edges (roads) takes O(E log E) time, where E is the number of edges. The Union-Find operations (checking group membership and merging groups) take approximately O(E * alpha(V)) time in total, where V is the number of cities (vertices) and alpha(V) is the inverse Ackermann function, which grows extremely slowly and can be considered nearly constant. Therefore, the overall time complexity is approximately O(E log E + E * alpha(V)). Since E log E will dominate E * alpha(V), it simplifies to O(E log E).

Space Complexity

O(N) – The algorithm uses the Union-Find data structure (implied by the 'groups' concept) to track which cities belong to which connected components. This typically involves an array of size N, where N is the number of cities, to store the parent or representative of each city's group. Therefore, the auxiliary space is dominated by this Union-Find data structure, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty city list	Return 0 immediately as there are no cities to connect.
Only one city in the list	Return 0 immediately since there are no connections needed.
All cities are already connected (cost is 0)	The algorithm should correctly identify this scenario and return 0 after initial processing if all needed connections already exist in the 'already connected' input.
No possible way to connect all cities (disconnected graph)	Return -1 (or throw an exception) if the minimum spanning tree algorithm determines that not all cities can be connected.
Large number of cities that causes integer overflow when summing costs	Use long or appropriate data type that can handle the potentially large sum of connection costs.
Edge costs are negative (invalid input)	Handle invalid negative edge costs by throwing an IllegalArgumentException or similar error.
Duplicate edges with different costs between two cities	The algorithm should choose the minimum cost edge between any two cities.
The cost matrix is not symmetric or is malformed.	Validate the cost matrix ensuring that cost[i][j] == cost[j][i] and handle exceptions accordingly if violated.