Minimum Cost to Connect All Points
You are given an array, ‘COORDINATES’ that represents the integer coordinates of some points on a 2D plane. Your task is to find the minimum cost to make all the points connected where the cost of connecting two points: (x1, y1) and (x2, y2) is equal to the manhattan distance between them, i.e., |x1 - x2| + |y1 - y2|.

Note:

1) An element of the ‘COORDINATES’ array is a pair of ‘X' and ‘Y’ coordinates of a point, i.e., COORDINATES[i] = (Xi, Yi). 2) |DISTANCE| represents the absolute value of distance. 3) All points are considered to be connected if there is exactly one simple path between two points. 4) According to Wikipedia, a simple path is a path in a plane that does not have repeating points.

Input Format

The first line of input contains an integer 'T' representing the number of test cases. The first line of each test case contains an integer ‘N’ representing the number of points in the ‘COORDINATES’ array. The next ‘N’ lines of each test case contain two space-separated integers representing the ‘X and ‘Y’ coordinates of a point.

Output Format:

For each test case, print a single line containing a single integer denoting the minimum cost to make all the points connected. The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Minimum Cost to Connect All Points

You are given an array, ‘COORDINATES’ that represents the integer coordinates of some points on a 2D plane. Your task is to find the minimum cost to make all the points connected where the cost of connecting two points: (x1, y1) and (x2, y2) is equal to the manhattan distance between them, i.e., |x1 - x2| + |y1 - y2|.

Note:

1) An element of the ‘COORDINATES’ array is a pair of ‘X' and ‘Y’ coordinates of a point, i.e., COORDINATES[i] =  (Xi, Yi).

2) |DISTANCE| represents the absolute value of distance.

3) All points are considered to be connected if there is exactly one simple path between two points.

4) According to Wikipedia, a simple path is a path in a plane that does not have repeating points.

Input Format

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains an integer ‘N’ representing the number of points in the ‘COORDINATES’ array.

The next ‘N’ lines of each test case contain two space-separated integers representing the ‘X and ‘Y’ coordinates of a point.

Output Format:

For each test case, print a single line containing a single integer denoting the minimum cost to make all the points connected.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 1000
10 ^ -6 <= X, Y <= 10 ^ 6
All points are distinct.

Where ‘T’ is the number of test cases, ‘N’ is the number of points in the ‘COORDINATES’ array, ‘X’, ‘Y’ is the x and y coordinates of a point, respectively.

Time limit: 1 sec.

Accepted Answer

Approach (Using Kruskal's Algo) :

1) First, we will add all the edges (that can be formed by any two points) and their cost in a min-heap.

2) Now, we will process each and every edge present in the min-heap one by one.

3) If the current edge in processing forms a cycle in the MST, then discard the edge; otherwise, include it in the MST. We will be adding the cost of edges included in the MST in an integer variable, ‘result’.

4) The process will be repeated till ‘n - 1’ edges are not included in the MST, where ‘n’ is the number of points in the ‘coordinates’ array. In the end, the ‘result’ will have the cost of MST so formed.

TC : O((N ^ 2) * (log (N)), where ‘N’ is the size of ‘coordinates’ array.
SC : O(N ^ 2)

Accepted Answer

Kruskal’s Algorithm

The problem indirectly refers to finding the cost of the minimum spanning tree of the graph formed by given points.

By definition, a minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices, without any cycles and with the minimum possible total edge weight. For ‘n’ vertices, an MST has ‘n - 1’ edges.

The idea is to use Kruskal’s Algorithm to find the MST for this problem.

First, we will add all the edges (that can be formed by any two points) and their cost in a min-heap. Now, we will process each and every edge present in the min-heap one by one. Min heap ensures that edges are processed in non-decreasing order of their cost.

If the current edge in processing forms a cycle in the MST, then discard the edge; otherwise, include it in the MST. We will be adding the cost of edges included in the MST in an integer variable, ‘result’.

The process will be repeated till ‘n - 1’ edges are not included in the MST, where ‘n’ is the number of points in the ‘coordinates’ array. In the end, the ‘result’ will have the cost of MST so formed.

Note:

We will use the Disjoint Set data structure to check for cycles in the MST build so far.
After ‘n - 1’ edges are included in the MST, all points will be connected. So, there is no need for further processing.

Algorithm:

Declare two integer variables, ‘result’ and ‘count’, and initialize with zero. The ‘result’ will hold the cost of the MST, and ‘count’ will hold the number of edges included in the MST.
Create a ‘vector’ of ‘array’ of size 3 (in C++), ‘edges’ to store three elements, ‘distance’, ‘i’ and ‘j’ where ‘i’ and ‘j’ are vertices, and ‘distance’ is the distance between them.
Run a loop from i = 0 to n - 1.
- Run a loop from j = i + 1 to n - 1.
  - Calculate the distance between the ‘i’th point and ‘j’th point present in the ‘coordinates’ array and store it in the variable ‘distance’.
  - Push {distance, i, j} in the ‘edges.
Build a min-heap, ‘pq’ by passing the contents of ‘edges’ in its constructor. The min heap will make the comparison according to ‘distance’.
Create an object ‘ds’ of ‘DisjointSet’ and pass ‘n’ as the parameter.
Run a loop while count < n - 1.
- Extract the element with minimum ‘distance’ from ‘pq’ and store it in the variable, ‘topElement’. Then, pop the top element from ‘pq’.
- From ‘topElement’, store the values of distance and vertices in variables ‘cost’, ‘u’ and ‘v’. (‘u’ and ‘v’ are vertices, and ‘cost’ is the distance/cost between them).
- If ds.find(u) != ds.find(v), that shows that including the edge between ‘u’ and ‘v’ will not produce a cycle in the MST. The ‘find’ function finds the representative element of a set. (If the representative element of both vertices is same, it implies they are already present in the same set, and there is a path connecting them. So, adding them again will produce a cycle).
  - Add ‘cost’ in the ‘result’.
  - Include the edge between ‘u’ and ‘v’ in the MST by ds.Union(u, v), which takes the union of ‘u’ and ‘v’.
  - Increment count by 1.
At the end, return ‘result’.

Description of ‘DisjointSet’ class

private:

The private part of the ‘DisjointSet’ class will contain two data members:

parent: An integer array to store the parent of each vertex in the graph.
rank: An integer array to store the rank of each vertex in the graph.

public:

The private part of the ‘DisjointSet’ class will contain one constructor and two member functions:

Description of ‘DisjointSet’ constructor

The constructor will take one parameter:

n: An integer variable that represents the number of vertices in the graph (i.e., number of points in the ‘coordinates’ array).

DisjointSet(n):

Resize the size of the ‘parent’ and ‘rank’ array to ‘n’.
Run a loop from i = 0 to n - 1.
- Assign ‘i’ to ‘parent[i]’ and set ‘rank[i]’ to zero.

Description of ‘find’ function

The function will take one parameter:

x: An integer variable that represents the vertex (element) whose representative element has to be searched.

find(x):

If parent[x] == x that shows that ‘x’ itself is the representative element. So, return ‘x’.
Else, call the ‘find’ function for ‘parent[x]’ and store the returned result in ‘parent[x]’.
Return ‘parent[x]’.

Description of ‘Union’ function

The function will take two parameters:

u: An integer variable that represents vertex in the graph (or point in ‘coordinates’ array).
v : Another integer variable that represents vertex in the graph (or point in ‘coordinates’ array).

Union(u, v):

Pass ‘u’ to the ‘find’ function and store the returned value in an integer variable, ‘uRep’.
Pass ‘v’ to the ‘find’ function and store the returned value in an integer variable, ‘vRep’.
If uRep == vRep that shows ‘u’ and ‘v’ are already in the same set. So, return.
Else if rank[uRep] < rank[vRep] that shows that the rank of ‘uRep’ is less than the rank of ‘vRep’.
- Update parent of ‘uRep’ by ‘vRep’.
Else if rank[uRep] > rank[vRep] that shows that the rank of ‘uRep’ is more than the rank of ‘vRep’.
- Update parent of ‘vRep’ by ‘uRep’.
Else rank of ‘uRep’ and ‘vRep’ are same.
- Update parent of ‘uRep’ by ‘vRep’.
- Increment rank of ‘vRep’ by 1.

Space Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the size of ‘coordinates’ array.

The ‘edges’ and ‘pq’ both require O(N ^ 2) space to store all the edges. The ‘ds’ requires O(N) space for the ‘parent’ and ‘rank’ array. Hence, overall space complexity is 2 * O(N ^ 2) + 2 * O(N) = O(N ^ 2).

Time Complexity: O(n^2logn)Explanation:

O((N ^ 2) * (log (N)), where ‘N’ is the size of ‘coordinates’ array.

The time complexity of inserting all the edges and the distance between them in ‘edges’ is O(N ^ 2) since two nested loops have been used.

The time complexity of building a min-heap using ‘edges’ is O(N).

At the end, for processing the edges, the while loop may run ‘N ^ 2’ times. As we have a complete graph, the total number of edges is ‘N * (N - 1) / 2’. So, we have to process every edge in the worst case. Also, in each iteration, the ‘find’ function is called, which can take O(log(N)) time in the worst case.

Hence, overall time complexity is O(N ^ 2) + O(N) + O((N ^ 2) * (log (N)) = O((N ^ 2) * (log (N)).

Python (3.5)

'''

	Time Complexity  :   O((N ^ 2) * (log (N))

    Space Complexity :   O(N ^ 2)



    Where ‘N’ is the size of ‘coordinates’ array.

'''

 

class DisjointSet:

 

    def __init__(self, vertices):

        self.V = vertices

        self.graph = []  

 

    # Function to add an edge to graph.

    def addEdge(self, u, v, w):

        self.graph.append([u, v, w])

 

    # A utility function to find set of an element i.

    def find(self, parent, i):

        if parent[i] == i:

            return i

        return self.find(parent, parent[i])

 

    # A function that does union of two sets of x and y.

    def union(self, parent, rank, x, y):

        xroot = self.find(parent, x)

        yroot = self.find(parent, y)

 

        if rank[xroot] < rank[yroot]:

            parent[xroot] = yroot

        elif rank[xroot] > rank[yroot]:

            parent[yroot] = xroot

 

        else:

            parent[yroot] = xroot

            rank[xroot] += 1

 

    # The main function to construct MST using Kruskal's algorithm.

    def KruskalMST(self):

 

        result = []

        i = 0

        e = 0

 

        self.graph = sorted(self.graph, key=lambda item: item[2])

 

        parent = []

        rank = []

 

        # Create V subsets with single elements.

        for node in range(self.V):

            parent.append(node)

            rank.append(0)

 

        # Number of edges to be taken is equal to V-1.

        while e < self.V - 1:

 

            u, v, w = self.graph[i]

            i = i + 1

            x = self.find(parent, u)

            y = self.find(parent, v)

 

            if x != y:

                e = e + 1

                result.append([u, v, w])

                self.union(parent, rank, x, y)

            # Else discard the edge.

 

        minimumCost = 0

        

        for u, v, weight in result:

            minimumCost += weight

            

        return minimumCost



def minimumCost(coordinates, n):

	

    g = DisjointSet(n)

    

    # Calculating edge values.

    for i in range (n - 1):

        for j in range (i + 1, n):

            distance = abs(coordinates[i][0] - coordinates[j][0]) + abs(coordinates[i][1] - coordinates[j][1])

            g.addEdge(i, j, distance)

            

    result = g.KruskalMST()

    return result

C++ (g++ 5.4)

/*

    Time Complexity  :   O((N ^ 2) * (log (N))

    Space Complexity :   O(N ^ 2)



    Where ‘N’ is the size of ‘coordinates’ array.

*/



#include 

#include 



// 'Disjoint Set' Class.

class DisjointSet

{

    vector parent, rank;



public:

    DisjointSet(int n)

    {

        parent.resize(n);

        rank.resize(n);



        for (int i = 0; i < n; i++)

        {

            parent[i] = i;

            rank[i] = 0;

        }

    }



    // Function to find the representative element of 'x'.

    int find(int x)

    {

        if (parent[x] == x)

        {

            return x;

        }

        return parent[x] = find(parent[x]);

    }



    // Function to put elements 'u' and 'v' in the same set.

    void Union(int u, int v)

    {

        int uRep = find(u);

        int vRep = find(v);



        if (uRep == vRep)

        {

            return;

        }



        if (rank[uRep] < rank[vRep])

        {

            parent[uRep] = vRep;

        }

        else if (rank[uRep] > rank[vRep])

        {

            parent[vRep] = uRep;

        }

        else

        {

            parent[uRep] = vRep;

            rank[vRep]++;

        }

    }

};



int minimumCost(vector> &coordinates, int n)

{

    int result = 0, count = 0;



    vector> edges;



    // Storing all the edges and their cost in 'edges'.

    for (int i = 0; i < n; i++)

    {

        for (int j = i + 1; j < n; j++)

        {

            int distance = abs(coordinates[i][0] - coordinates[j][0]) + abs(coordinates[i][1] - coordinates[j][1]);

            edges.push_back({distance, i, j});

        }

    }



    // Inserting all the edges in a min-heap.

    priority_queue, vector>, greater>> pq(edges.begin(), edges.end());



    // Creating an object of 'DisjointSet' class.

    DisjointSet ds(n);



    // Processing edges till 'n - 1' edges are included in the MST.

    while (count < n - 1)

    {

        array topElement = pq.top();

        pq.pop();



        int cost = topElement[0], u = topElement[1], v = topElement[2];



        // Checking whether adding the edge between 'u' and 'v' will create a cycle or not.

        if (ds.find(u) != ds.find(v))

        {

            result = result + cost;

            ds.Union(u, v);

            count++;

        }

    }

    return result;

}

Java (SE 1.8)

/*

    Time Complexity  :   O((N ^ 2) * (log (N))

    Space Complexity :   O(N ^ 2)



    Where 'N' is the size of 'coordinates' array.

*/



import java.util.ArrayList;

import java.util.PriorityQueue;



// 'Disjoint Set' Class.

class DisjointSet {

	ArrayList parent, rank;



	DisjointSet(int n) {

		parent = new ArrayList<>(n);

		rank = new ArrayList<>(n);



		for (int i = 0; i < n; i++) {

			parent.add(i);

			rank.add(i);



		}

	}



	// Function to find the representative element of 'x'.

	int find(int x) {

		if (parent.get(x) == x) {

			return x;

		}



		parent.set(x, find(parent.get(x)));

		return parent.get(x);

	}



	// Function to put elements 'u' and 'v' in the same set.

	void union(int u, int v) {

		int uRep = find(u);

		int vRep = find(v);



		if (uRep == vRep) {

			return;

		}



		if (rank.get(uRep) < rank.get(vRep)) {

			parent.set(uRep, vRep);

		} else if (rank.get(uRep) > rank.get(vRep)) {

			parent.set(vRep, uRep);

		} else {

			parent.set(uRep, vRep);

			rank.set(vRep, rank.get(vRep) + 1);

		}

	}

}



public class Solution {

	public static int minimumCost(int[][] coordinates, int n) {

		int result = 0, count = 0;



		ArrayList edges = new ArrayList<>();



		// Storing all the edges and their cost in 'edges'.

		for (int i = 0; i < n; i++) {

			for (int j = i + 1; j < n; j++) {

				int distance = Math.abs(coordinates[i][0] - coordinates[j][0])

						+ Math.abs(coordinates[i][1] - coordinates[j][1]);

				int[] temp = new int[3];

				temp[0] = distance;

				temp[1] = i;

				temp[2] = j;

				edges.add(temp);

			}

		}



		// Inserting all the edges in a min-heap.

		PriorityQueue pq = new PriorityQueue<>(3, (a, b) -> a[0] - b[0]);

		for (int i = 0; i < edges.size(); i++) {

			pq.add(edges.get(i));

		}



		// Creating an object of 'DisjointSet' class.

		DisjointSet ds = new DisjointSet(n);



		// Processing edges till 'n - 1' edges are included in the MST.

		while (count < n - 1) {

			int[] topElement = pq.peek();

			pq.remove();



			int cost = topElement[0], u = topElement[1], v = topElement[2];



			// Checking whether adding the edge between 'u' and 'v' will create a cycle or not.

			if (ds.find(u) != ds.find(v)) {

				result = result + cost;

				ds.union(u, v);

				count++;

			}

		}



		return result;

	}

}

Accepted Answer

Optimized Prim's Algorithm

Since we are dealing with the complete graph, the total number of edges is ‘n * (n - 1) / 2’, which is in the order of ‘n ^ 2’. But our MST will contain only ‘n - 1’ edges that implies that in the previous approach, the min-heap is also storing the edges which are not relevant.The idea is to keep track of the minimal distance to each vertex using a ‘cost’ array which is updated with every addition of vertex in MST. So, a min-heap is no longer required.

In this approach, first, we will choose a source vertex (‘src’) and update its cost in the ‘cost’ array by ‘INT_MAX’ so that it is never picked again and include it in the MST by marking it visited. Then, we will find the distance of every vertex from the ‘src’ and update it in the ‘cost’ array. While doing so, we can keep track of the minimal distance vertex (say: ‘nextMin’) from ‘src’. Add the cost of ‘nextMin’ in the ‘result’ (‘result’ variable will hold the final cost of MST) and use ‘nextMin’ as new ‘src’ to find the minimal distance from it. Repeat this process till ‘n - 1’ vertices are included in the MST.

Algorithm:

Declare two integer variables, ‘result’ and ‘count’, and initialize with zero. The ‘result’ will hold the cost of the MST, and ‘count’ will hold the number of edges included in the MST.
Declare a boolean array, ‘visited’ of size ‘n’ to keep track of the vertices included in the MST.
Declare an integer array, ‘cost’ of size ‘n’ and initialize it with ‘INT_MAX’. It will represent the minimum distance to the current spanning tree.
Declare an integer variable, ‘src’, and initialize it with zero. It represents that zero is chosen as the source vertex.
Run a loop while count < n - 1.
- Mark the ‘src’ as visited.
- Update ‘cost’ of ‘src’ by ‘INT_MAX’.
- Declare an integer variable, ‘nextMin’ representing the next vertex to be added in MST which has minimal distance from ‘src’. Initially, assign ‘src’ to ‘nextMin’.
- Run a loop from i = 0 to n - 1.
  - If visited[i] == true that shows that vertex, ‘i’ has been already visited.
    - So, skip the below steps.
  - Else, calculate the distance between the ‘i’th vertex and ‘src’ vertex present in the ‘coordinates’ array and store it in the variable ‘distance’.
  - Update the cost of ‘i’th vertex by the minimum of ‘cost[i]’ and ‘distance’.
  - If cost[nextMin] > cost[i] that shows that ‘i’th vertex has less cost from ‘src’ compared to ‘nextMin’
    - Update ‘nextMin’ by ‘i’.
- Add ‘cost[nextMin]’ to the ‘result’.
- Update ‘src’ by ‘nextMin’.
- Increment ‘count’ by 1.
In the end, return ‘result’.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the size of the ‘coordinates’ array.

Since O(N) space is required for the ‘visited’ and ‘cost’ array.

Time Complexity: O(n^2)Explanation:

O((N ^ 2)), where ‘N’ is the size of ‘coordinates’ array.

Since the while loop will make ‘N - 1’ iterations and in every iteration the for loop will run ‘N’ times. Hence, overall time complexity is O((N - 1) * N) = O((N ^ 2) - N) = O (N ^ 2).

Python (3.5)

'''

	Time Complexity  :   O(N ^ 2)

    Space Complexity :   O(N)



    Where ‘N’ is the size of ‘coordinates’ array.

'''



def minimumCost(coordinates, n):

	

    result = 0

    count = 0

    

    visited = [0] * n

    cost = [10 ** 9 for i in range (n)]

    

    # Index of the source vertex.

    src = 0

    while count < n - 1:

        visited[src] = 1

        cost[src] = 10 ** 9

        

        # To store the index of minimum cost vertex from 'src'.

        nextMin = src

        

        for i in range (n):

            if visited[i]:

                continue

            

            distance = abs(coordinates[i][0] - coordinates[src][0]) + abs(coordinates[i][1] - coordinates[src][1])

            

            # Relax the cost of edge connecting 'i' and 'src'.

            cost[i] = min(cost[i], distance)

            

            if cost[nextMin] > cost[i]:

                nextMin = i

                

        result += cost[nextMin]

        

        src = nextMin

        count += 1

        

    return result

Java (SE 1.8)

/*

    Time Complexity  :   O(N ^ 2)

    Space Complexity :   O(N)



    Where 'N' is the size of 'coordinates' array.

*/



import java.util.ArrayList;



public class Solution {

	public static int minimumCost(int[][] coordinates, int n) {

		int result = 0, count = 0;



		ArrayList visited = new ArrayList<>(n);

		for (int i = 0; i < n; i++) {

			visited.add(false);

		}

		

		ArrayList cost = new ArrayList<>(n);

		for (int i = 0; i < n; i++) {

			cost.add(Integer.MAX_VALUE);

		}



		// Index of source vertex.

		int src = 0;



		// Processing edges till 'n - 1' edges are included in the MST.

		while (count < n - 1) {

			visited.set(src, true);

			cost.set(src, Integer.MAX_VALUE);



			// To store the index of minimum cost vertex from 'src'.

			int nextMin = src;



			for (int i = 0; i < n; i++) {

				if (visited.get(i) == true) {

					continue;

				}



				int distance = Math.abs(coordinates[i][0] - coordinates[src][0])

						+ Math.abs(coordinates[i][1] - coordinates[src][1]);



				// Relax the cost of edge connecting 'i' and 'src'.

				cost.set(i, Math.min(cost.get(i), distance));



				// Update the index of minimum cost vertex.

				if (cost.get(nextMin) > cost.get(i)) {

					nextMin = i;

				}

			}



			result = result + cost.get(nextMin);



			// Update the source by index of minimum cost vertex from 'src' for next iteration.

			src = nextMin;



			count++;

		}



		return result;

	}

}

C++ (g++ 5.4)

/*

    Time Complexity  :   O(N ^ 2)

    Space Complexity :   O(N)



    Where ‘N’ is the size of ‘coordinates’ array.

*/



#include 



int minimumCost(vector> &coordinates, int n)

{

    int result = 0, count = 0;



    vector visited(n);

    vector cost(n, INT_MAX);



    // Index of source vertex.

    int src = 0;



    // Processing edges till 'n - 1' edges are included in the MST.

    while (count < n - 1)

    {

        visited[src] = true;

        cost[src] = INT_MAX;



        // To store the index of minimum cost vertex from 'src'.

        int nextMin = src;



        for (int i = 0; i < n; i++)

        {

            if (visited[i] == true)

            {

                continue;

            }



            int distance = abs(coordinates[i][0] - coordinates[src][0]) + abs(coordinates[i][1] - coordinates[src][1]);



            // Relax the cost of edge connecting 'i' and 'src'.

            cost[i] = min(cost[i], distance);



            // Update the index of minimum cost vertex.

            if (cost[nextMin] > cost[i])

            {

                nextMin = i;

            }

        }



        result = result + cost[nextMin];



        // Update the source by index of minimum cost vertex from 'src' for next iteration.

        src = nextMin;



        count++;

    }

    return result;

}

Note:

Input Format

Output Format:

Note:

Constraints:

Top Oracle Application Developer interview questions & answers

Popular interview questions of Application Developer

Top HR questions asked in Oracle Application Developer