{"id":7367,"date":"2020-09-13T00:22:16","date_gmt":"2020-09-13T07:22:16","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7367"},"modified":"2020-09-13T00:46:41","modified_gmt":"2020-09-13T07:46:41","slug":"leetcode-1584-min-cost-to-connect-all-points","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1584-min-cost-to-connect-all-points\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1584. Min Cost to Connect All Points"},"content":{"rendered":"\n

You are given an array points<\/code> representing integer coordinates of some points on a 2D-plane, where points[i] = [xi<\/sub>, yi<\/sub>]<\/code>.<\/p>\n\n\n\n

The cost of connecting two points [xi<\/sub>, yi<\/sub>]<\/code> and [xj<\/sub>, yj<\/sub>]<\/code> is the manhattan distance<\/strong> between them: |xi<\/sub> - xj<\/sub>| + |yi<\/sub> - yj<\/sub>|<\/code>, where |val|<\/code> denotes the absolute value of val<\/code>.<\/p>\n\n\n\n

Return the minimum cost to make all points connected.<\/em> All points are connected if there is exactly one<\/strong> simple path between any two points.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> points = [[0,0],[2,2],[3,10],[5,2],[7,0]]\nOutput:<\/strong> 20\nExplanation:\n<\/strong>\nWe can connect the points as shown above to get the minimum cost of 20.\nNotice that there is a unique path between every pair of points.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> points = [[3,12],[-2,5],[-4,1]]\nOutput:<\/strong> 18\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> points = [[0,0],[1,1],[1,0],[-1,1]]\nOutput:<\/strong> 4\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> points = [[-1000000,-1000000],[1000000,1000000]]\nOutput:<\/strong> 4000000\n<\/pre>\n\n\n\n
Example 5:<\/strong><\/p>\n\n\n\n
Input:<\/strong> points = [[0,0]]\nOutput:<\/strong> 0\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= points.length <= 1000<\/code><\/li>
  • -106<\/sup> <= xi<\/sub>, yi<\/sub> <= 106<\/sup><\/code><\/li>
  • All pairs (xi<\/sub>, yi<\/sub>)<\/code> are distinct.<\/li><\/ul>\n\n\n\n
    Solution: Minimum Spanning Tree<\/strong><\/h2>\n\n\n\n
    Kruskal’s algorithm 
    Time complexity: O(n^2logn) 
    Space complexity: O(n^2)
    using vector of vector, array, pair of pair, or tuple might lead to TLE…<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nstruct Edge {\n  int cost;\n  int x;\n  int y;\n  bool operator<(const Edge& e) const { return cost < e.cost; }\n};\nclass Solution {\npublic:\n  int minCostConnectPoints(vector>& points) {\n    const int n = points.size();\n    vector edges(n * (n - 1) \/ 2); \/\/ {cost, i, j}\n    for (int i = 0, idx = 0; i < n; ++i)\n      for (int j = i + 1; j < n; ++j)\n        edges[idx++] = {abs(points[i][0] - points[j][0]) + \n                        abs(points[i][1] - points[j][1]), i, j};\n    std::sort(begin(edges), end(edges));\n    vector p(n); \n    std::iota(begin(p), end(p), 0);\n    vector rank(n, 0);\n    int ans = 0;\n    int count = 0;\n    for (const auto& e : edges) {          \n      int rx = find(p, e.x);\n      int ry = find(p, e.y);\n      if (rx == ry) continue;\n      ans += e.cost;\n      if (rank[rx] < rank[ry]) swap(rx, ry);\n      p[rx] = ry;\n      rank[ry] += rank[rx] == rank[ry];\n      if (++count == n - 1) break;\n    }\n    return ans;\n  }\nprivate:\n  int find(vector& p, int x) const {   \n    while (p[x] != x) {\n      int tp = p[x];\n      p[x] = p[p[x]];\n      x = tp;\n    }\n    return x;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    Prim’s Algorithm 
    ds[i] := min distance from i to ANY<\/strong> nodes in the tree.<\/p>\n\n\n\n
    Time complexity: O(n^2) Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  int minCostConnectPoints(vector>& points) {\n    const int n = points.size();\n    auto dist = [](const vector& pi, const vector& pj) {\n      return abs(pi[0] - pj[0]) + abs(pi[1] - pj[1]);\n    };\n    vector ds(n, INT_MAX);  \n    for (int i = 1; i < n; ++i)\n      ds[i] = dist(points[0], points[i]);\n    \n    int ans = 0;\n    for (int i = 1; i < n; ++i) {\n      auto it = min_element(begin(ds), end(ds));\n      const int v = distance(begin(ds), it);\n      ans += ds[v];      \n      ds[v] = INT_MAX; \/\/ done\n      for (int i = 0; i < n; ++i) {\n        if (ds[i] == INT_MAX) continue;\n        ds[i] = min(ds[i], dist(points[i], points[v]));\n      }        \n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi]. The cost of connecting two points [xi, yi] and [xj, yj] is…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[77,177,533],"class_list":["post-7367","post","type-post","status-publish","format-standard","hentry","category-graph","tag-graph","tag-medium","tag-mst","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7367","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7367"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7367\/revisions"}],"predecessor-version":[{"id":7373,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7367\/revisions\/7373"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7367"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7367"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7367"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}