LeetCode 1135: Connecting Cities With Minimum Cost Solution

Master LeetCode problem 1135 (Connecting Cities With Minimum Cost), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1135. Connecting Cities With Minimum Cost

Medium

Union Find Graph Heap (Priority Queue)Minimum Spanning Tree

Problem Explanation

Explanation:

Given a list of connections between cities and their costs, we need to find the minimum cost to connect all cities such that there is at least one path between any two cities.

To solve this problem, we can use Kruskal's algorithm, which is a minimum spanning tree algorithm. The idea is to sort the connections based on their costs in ascending order and then iterate through them to build the minimum spanning tree.

Algorithm:

Sort the connections based on their costs.
Initialize an array to keep track of the parent of each city.
Initialize a variable to keep track of the total cost.
Iterate through the sorted connections:
- Find the parents of the two cities connected by the current connection.
- If the two cities have different parents, update the parent of one city to be the parent of the other city and add the cost of the connection to the total cost.
After processing all connections, check if all cities are connected. If not, return -1.

Time Complexity: O(ElogE) where E is the number of connections Space Complexity: O(N) where N is the number of cities

: :

Solution Code

class Solution {
    public int minimumCost(int N, int[][] connections) {
        Arrays.sort(connections, (a, b) -> a[2] - b[2]);
        
        int[] parent = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            parent[i] = i;
        }
        
        int totalCost = 0;
        int numEdges = 0;
        
        for (int[] connection : connections) {
            int city1 = connection[0];
            int city2 = connection[1];
            int cost = connection[2];
            
            int parent1 = find(city1, parent);
            int parent2 = find(city2, parent);
            
            if (parent1 != parent2) {
                parent[parent1] = parent2;
                totalCost += cost;
                numEdges++;
            }
        }
        
        return numEdges == N - 1 ? totalCost : -1;
    }
    
    private int find(int city, int[] parent) {
        while (city != parent[city]) {
            parent[city] = parent[parent[city]];
            city = parent[city];
        }
        return city;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1135 (Connecting Cities With Minimum Cost)?

This page provides optimized solutions for LeetCode problem 1135 (Connecting Cities With Minimum Cost) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1135 (Connecting Cities With Minimum Cost)?

The time complexity for LeetCode 1135 (Connecting Cities With Minimum Cost) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1135 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1135 in Java, C++, or Python.

Back to LeetCode Solutions