Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Min Cost to Connect All Points
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [x<sub>i</sub>, y<sub>i</sub>].

The cost of connecting two points [x<sub>i</sub>, y<sub>i</sub>] and [x<sub>i</sub>, y<sub>i</sub>] is the Manhattan distance between them: |x<sub>i</sub> - x<sub>i</sub>| + |y<sub>i</sub> - y<sub>i</sub>|, where |val| denotes the absolute value of val.

Return the minimum cost to connect all the points such that each point is connected directly or indirectly to every other point with exactly one simple path between any two points.

Examples

  1. Example 1:
    • Input: points = [[1, 1], [2, 2], [2, 4], [3, 3]]
    • Expected Output: 6
Image
  • Justification: The optimal connections are [(1,1) -> (2,2)], [(2,2) -> (3,3)] and [(2,2) -> (2,4)] with distances 2, 2 and 2 respectively, summing up to 6.
  1. Example 2:
    • Input: points = [[0, 0], [1, 2], [3, 3]]
    • Expected Output: 6
Image
  • Justification: The optimal connections are [(0,0) -> (1,2)] and [(1,2) -> (3,3)] with distances 3 and 3 respectively, summing up to 6.
  1. Example 3:
    • Input: points = [[0, 0], [2, 4], [4, 2], [6, 6]]
    • Expected Output: 16
Image
  • Justification: The optimal connections are [(0,0) -> (2,4)], [(2,4) -> (4,2)] and [(4,2) -> (6,6)] with distances 6, 4 and 6 respectively, summing up to 16.

Constraints:

  • 1 <= points.length <= 1000
  • -10<sup>6</sup> <= x<sub>i</sub>, y<sub>i</sub> <= 10<sup>6</sup>
  • All pairs (x<sub>i</sub>, y<sub>i</sub>) are distinct.

Solution

To solve this problem, we will use Prim's algorithm. Prim's algorithm helps us find the Minimum Spanning Tree (MST) for a graph, which connects all points with the minimum possible total edge cost. The reason Prim's algorithm is suitable here is that it effectively builds the MST by always extending the tree with the least costly edge available, ensuring the minimum connection cost is maintained at each step.

The approach begins by treating one point as the starting node and iteratively adding the nearest point that is not yet connected to the growing MST. We use a priority queue to always pick the least costly edge and keep track of the total cost until all points are connected. This method ensures the most efficient way to connect all points while minimizing the overall connection cost.

Step-by-step Algorithm

  1. Initialization:

    • Create a boolean array inMST of size n to keep track of nodes included in the MST.
    • Create an integer array minDist of size n to store the minimum distance from the MST to each node.
    • Set minDist[0] to 0 (starting point) and all other entries to Integer.MAX_VALUE (infinity).

  2. MST Construction:

    • Initialize mstCost to 0 to store the total cost of the MST.
    • Initialize edgesUsed to 0 to keep track of the number of edges added to the MST.

  3. Main Loop (until all nodes are included in the MST):

    • Find the node with the minimum distance that is not yet in the MST (currNode).
      • Initialize currMinEdge to Integer.MAX_VALUE and currNode to -1.
      • Loop through each node, and if it is not in the MST and its distance is less than currMinEdge, update currMinEdge and currNode.
    • Add the cost of this node (currMinEdge) to mstCost.
    • Mark this node as included in the MST (inMST[currNode] = true).
    • Increment edgesUsed by 1.

  4. Update Distances:

    • For each node that is not in the MST:
      • Calculate the Manhattan distance from currNode to this node.
      • If this distance is less than the current value in minDist for this node, update minDist.

  5. Repeat steps 3 and 4 until all nodes are included in the MST.

  6. Return the total cost of the MST (mstCost).

Algorithm Walkthrough

Let's walk through the algorithm with the input [[1, 1], [2, 2], [2, 4], [3, 3]].

Image

  1. Initialization:

    • inMST = [false, false, false, false]
    • minDist = [0, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE]
    • mstCost = 0
    • edgesUsed = 0

  2. First Iteration:

    • Find currNode:
      • Node 0 has minDist[0] = 0 (smallest, not in MST)
      • currNode = 0, currMinEdge = 0
    • Update MST:
      • mstCost = 0 + 0 = 0
      • inMST = [true, false, false, false]
      • edgesUsed = 1
    • Update Distances:
      • Calculate distance from node 0 to node 1: |1-2| + |1-2| = 2, update minDist[1] = 2
      • Calculate distance from node 0 to node 2: |1-2| + |1-4| = 4, update minDist[2] = 4
      • Calculate distance from node 0 to node 3: |1-3| + |1-3| = 4, update minDist[3] = 4
      • minDist = [0, 2, 4, 4]

  3. Second Iteration:

    • Find currNode:
      • Node 1 has minDist[1] = 2 (smallest, not in MST)
      • currNode = 1, currMinEdge = 2
    • Update MST:
      • mstCost = 0 + 2 = 2
      • inMST = [true, true, false, false]
      • edgesUsed = 2
    • Update Distances:
      • Calculate distance from node 1 to node 2: |2-2| + |2-4| = 2, update minDist[2] = 2
      • Calculate distance from node 1 to node 3: |2-3| + |2-3| = 2, update minDist[3] = 2
      • minDist = [0, 2, 2, 2]

  4. Third Iteration:

    • Find currNode:
      • Node 2 has minDist[2] = 2 (smallest, not in MST)
      • currNode = 2, currMinEdge = 2
    • Update MST:
      • mstCost = 2 + 2 = 4
      • inMST = [true, true, true, false]
      • edgesUsed = 3
    • Update Distances:
      • Calculate distance from node 2 to node 3: |2-3| + |4-3| = 2, no update needed as minDist[3] is already 2
      • minDist = [0, 2, 2, 2]

  5. Fourth Iteration:

    • Find currNode:
      • Node 3 has minDist[3] = 2 (smallest, not in MST)
      • currNode = 3, currMinEdge = 2
    • Update MST:
      • mstCost = 4 + 2 = 6
      • inMST = [true, true, true, true]
      • edgesUsed = 4

  6. All nodes included. Return mstCost = 6.

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

The time complexity of the Prim's algorithm implementation for the given problem is as follows:

  1. Initialization:

    • Initializing the minDist array takes O(N) time, where N is the number of points.

  2. Main Loop:

    • The while loop runs N times because we add one node to the MST in each iteration.
    • Inside the loop, finding the node with the minimum distance not yet in the MST takes O(N) time (linear scan of the minDist array).
    • The nested loop to update the minDist array also takes O(N) time for each node, resulting in an overall complexity of O(N^2).

Therefore, the overall time complexity is O(N^2).

Space Complexity

The space complexity is O(N) because we use arrays inMST and minDist, both of size N.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible