Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

157. Min Cost to Connect All Points

MediumDay 46 of 60Graphs

You are given points, where points[i] = [x, y] is a point on a 2D plane. Connecting two points costs their Manhattan distance abs(x1 - x2) + abs(y1 - y2). Return the minimum total cost to connect all points so that there is exactly one simple path between any two of them.

Example 1
Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
The cheapest set of connections forms a tree whose edges add up to 20.
Example 2
Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18
Constraints
  • 1 <= points.length <= 1000
  • -10^6 <= x, y <= 10^6
  • All points are distinct
Hints
Frequently asked at: Amazon, Google, Microsoft
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min