Average Salary Excluding the Minimum and Maximum Salary

Description

You are given an array points representing integer coordinates of some points on a 2D plane, where points[i] = [xi, yi].

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

In graph theory terms, the points form a complete weighted graph where the edge weight between any two points is their Manhattan distance. We need to find a Minimum Spanning Tree (MST) of this complete graph — a subset of edges that connects all vertices with the minimum possible total edge weight and without forming any cycle.

Examples

Example 1

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]

Output: 20

Explanation: We have 5 points: P0(0,0), P1(2,2), P2(3,10), P3(5,2), P4(7,0). The optimal connections use 4 edges:

P1 ↔ P3: |2−5| + |2−2| = 3
P0 ↔ P1: |0−2| + |0−2| = 4
P3 ↔ P4: |5−7| + |2−0| = 4
P1 ↔ P2: |2−3| + |2−10| = 9

Total cost = 3 + 4 + 4 + 9 = 20. This is the minimum cost spanning tree for these 5 points.

Example 2

Input: points = [[3,12],[-2,5],[-4,1]]

Output: 18

Explanation: We have 3 points: P0(3,12), P1(-2,5), P2(-4,1). The distances are:

P0 ↔ P1: |3−(−2)| + |12−5| = 5 + 7 = 12
P0 ↔ P2: |3−(−4)| + |12−1| = 7 + 11 = 18
P1 ↔ P2: |−2−(−4)| + |5−1| = 2 + 4 = 6

The MST picks edges P1↔P2 (cost 6) and P0↔P1 (cost 12), giving a total of 18.

Constraints

1 ≤ points.length ≤ 1000
-10⁶ ≤ xi, yi ≤ 10⁶
All pairs (xi, yi) are distinct.

Editorial

Brute Force - Kruskal's Algorithm

Intuition

This problem is fundamentally a Minimum Spanning Tree (MST) problem on a complete graph. Every pair of points has an edge whose weight is their Manhattan distance, and we want to select exactly n−1 edges that connect all n points with the smallest total weight.

The most direct approach uses Kruskal's Algorithm:

Enumerate every possible edge between all pairs of points.
Sort all these edges by weight (Manhattan distance) in ascending order.
Greedily pick the smallest edge that does not form a cycle with the edges already chosen.
Repeat until we have n−1 edges.

To efficiently detect whether adding an edge would form a cycle, we use a Union-Find (Disjoint Set Union) data structure. Initially, each point is its own component. When we add an edge connecting points u and v, we merge their components. If u and v are already in the same component, adding the edge would create a cycle, so we skip it.

With n points, there are n×(n−1)/2 edges in the complete graph. For n = 1000, that is about 500,000 edges. Sorting these takes O(n² log n) time, which is the bottleneck of this approach.

Step-by-Step Explanation

Let's trace through Example 1: points = [[0,0],[2,2],[3,10],[5,2],[7,0]].

Label the points P0(0,0), P1(2,2), P2(3,10), P3(5,2), P4(7,0).

Step 1 — Generate all edges: Compute Manhattan distance for every pair:

P0↔P1: 4, P0↔P2: 13, P0↔P3: 7, P0↔P4: 7
P1↔P2: 9, P1↔P3: 3, P1↔P4: 7
P2↔P3: 10, P2↔P4: 14
P3↔P4: 4
Total: 10 edges.

Step 2 — Sort edges: [P1↔P3:3, P0↔P1:4, P3↔P4:4, P0↔P3:7, P0↔P4:7, P1↔P4:7, P1↔P2:9, P2↔P3:10, P0↔P2:13, P2↔P4:14].

Step 3 — Process edge P1↔P3 (weight 3): P1 and P3 are in different components. Union them. MST cost = 3. Components: {P1,P3}, {P0}, {P2}, {P4}.

Step 4 — Process edge P0↔P1 (weight 4): P0 and P1 are in different components. Union them. MST cost = 7. Components: {P0,P1,P3}, {P2}, {P4}.

Step 5 — Process edge P3↔P4 (weight 4): P3 and P4 are in different components. Union them. MST cost = 11. Components: {P0,P1,P3,P4}, {P2}.

Step 6 — Process edge P0↔P3 (weight 7): P0 and P3 are already in the same component → skip (adding this would form a cycle).

Step 7 — Process edge P0↔P4 (weight 7): Same component → skip.

Step 8 — Process edge P1↔P4 (weight 7): Same component → skip.

Step 9 — Process edge P1↔P2 (weight 9): P1 and P2 are in different components. Union them. MST cost = 20. Components: {P0,P1,P2,P3,P4}.

Step 10: All 5 points are now connected with 4 edges. MST is complete. Return cost = 20.

Kruskal's Algorithm — Building MST Edge by Edge — Watch how Kruskal's algorithm sorts all edges by weight and greedily selects the smallest edge that does not form a cycle, using Union-Find to track connected components.

Algorithm

Generate all edges: for every pair of points (i, j) where i < j, compute the Manhattan distance |xi − xj| + |yi − yj| and store the edge as (weight, i, j). This produces n×(n−1)/2 edges.
Sort all edges in non-decreasing order of weight.
Initialize a Union-Find structure with n elements, one per point.
Initialize cost = 0 and edgesUsed = 0.
Iterate through sorted edges. For each edge (w, u, v):
a. If find(u) ≠ find(v) — u and v are in different components:
- Union u and v.
- Add w to cost.
- Increment edgesUsed.
- If edgesUsed == n − 1, break (MST is complete).
  b. Otherwise, skip the edge (it would form a cycle).
Return cost.

Code

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        vector<array<int, 3>> edges;

        // Generate all edges with Manhattan distance
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int dist = abs(points[i][0] - points[j][0]) 
                         + abs(points[i][1] - points[j][1]);
                edges.push_back({dist, i, j});
            }
        }

        // Sort edges by weight
        sort(edges.begin(), edges.end());

        // Union-Find with path compression and union by rank
        vector<int> parent(n), rnk(n, 0);
        iota(parent.begin(), parent.end(), 0);

        function<int(int)> find = [&](int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        };

        int cost = 0, edgesUsed = 0;
        for (auto& e : edges) {
            int w = e[0], u = e[1], v = e[2];
            int pu = find(u), pv = find(v);
            if (pu != pv) {
                if (rnk[pu] < rnk[pv]) swap(pu, pv);
                parent[pv] = pu;
                if (rnk[pu] == rnk[pv]) rnk[pu]++;
                cost += w;
                if (++edgesUsed == n - 1) break;
            }
        }

        return cost;
    }
};

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        edges = []

        # Generate all edges with Manhattan distance
        for i in range(n):
            for j in range(i + 1, n):
                dist = (abs(points[i][0] - points[j][0]) 
                      + abs(points[i][1] - points[j][1]))
                edges.append((dist, i, j))

        edges.sort()

        # Union-Find with path compression and union by rank
        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x: int, y: int) -> bool:
            px, py = find(x), find(y)
            if px == py:
                return False
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
            return True

        cost = 0
        edges_used = 0
        for w, u, v in edges:
            if union(u, v):
                cost += w
                edges_used += 1
                if edges_used == n - 1:
                    break

        return cost

class Solution {
    private int[] parent, rank;

    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        List<int[]> edges = new ArrayList<>();

        // Generate all edges with Manhattan distance
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int dist = Math.abs(points[i][0] - points[j][0])
                         + Math.abs(points[i][1] - points[j][1]);
                edges.add(new int[]{dist, i, j});
            }
        }

        edges.sort((a, b) -> a[0] - b[0]);

        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        int cost = 0, edgesUsed = 0;
        for (int[] edge : edges) {
            int w = edge[0], u = edge[1], v = edge[2];
            if (union(u, v)) {
                cost += w;
                edgesUsed++;
                if (edgesUsed == n - 1) break;
            }
        }

        return cost;
    }

    private int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    private boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank[px] < rank[py]) {
            int temp = px; px = py; py = temp;
        }
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n² log n)

Generating all edges takes O(n²). Sorting them takes O(n² log n²) = O(n² log n). Processing sorted edges with Union-Find (path compression + union by rank) takes nearly O(n²) amortized. The sorting step dominates, giving O(n² log n) overall.

Space Complexity: O(n²)

We store all n×(n−1)/2 edges explicitly, which is O(n²). The Union-Find structure uses O(n) space. Total: O(n²).

Why This Approach Is Not Efficient

Kruskal's algorithm works correctly but has two inefficiencies for this specific problem:

1. Sorting bottleneck: With n = 1000 points, we generate n×(n−1)/2 ≈ 500,000 edges and sort them all. The O(n² log n) sorting step is the bottleneck. But do we really need to see ALL edges in sorted order? The MST only uses n−1 edges, so most of the sorting effort is wasted.

2. Space overhead: Storing all 500,000 edges requires O(n²) memory. For larger inputs, this becomes significant.

The key insight is that this is a complete graph (every pair of points is connected). For dense graphs where the number of edges E is close to V², Prim's algorithm with a simple array (no priority queue) runs in O(V²) = O(n²) time — strictly better than Kruskal's O(n² log n). Furthermore, Prim's only needs O(n) space because it never constructs the full edge list.

Optimal Approach - Prim's Algorithm

Intuition

Prim's algorithm builds the MST by growing it from a single starting vertex, one edge at a time. At each step, it selects the cheapest edge that connects a vertex already in the MST to a vertex not yet in the MST.

Think of it like expanding a network from a central hub. You start at one point, then always extend a cable to the nearest unconnected point. After connecting that point, you recalculate which unconnected point is now closest to ANY point in your growing network (not just the original hub).

For a complete graph (where every pair of vertices is connected), we can implement Prim's efficiently without a priority queue:

Maintain an array minDist[v] that stores the minimum cost to connect vertex v to the current MST.
At each iteration, scan the array to find the unvisited vertex with the smallest minDist value. Add it to the MST.
After adding a vertex u to the MST, update minDist[v] for every unvisited vertex v: minDist[v] = min(minDist[v], manhattan(u, v)).

This avoids sorting entirely. Each of the n iterations does an O(n) scan to find the minimum and an O(n) update, giving O(n²) total time — better than Kruskal's O(n² log n) for complete graphs.

This approach works because of the cut property: the minimum weight edge crossing any cut (partition of vertices into MST and non-MST) must belong to some MST. By always picking the smallest minDist, we are always choosing the minimum cut edge.

Step-by-Step Explanation

Let's trace through Example 1: points = [[0,0],[2,2],[3,10],[5,2],[7,0]].

Step 1 — Initialization: Set minDist = [0, ∞, ∞, ∞, ∞]. Start with vertex 0 (minDist[0] = 0 so it is picked first). inMST = [F, F, F, F, F]. totalCost = 0.

Step 2 — Pick vertex 0 (minDist=0): Mark inMST[0] = true. totalCost += 0 = 0. Update neighbors:

minDist[1] = min(∞, dist(0,1)) = min(∞, 4) = 4
minDist[2] = min(∞, dist(0,2)) = min(∞, 13) = 13
minDist[3] = min(∞, dist(0,3)) = min(∞, 7) = 7
minDist[4] = min(∞, dist(0,4)) = min(∞, 7) = 7
Now minDist = [0, 4, 13, 7, 7].

Step 3 — Pick vertex 1 (minDist=4): Scan for minimum among unvisited: minDist[1]=4 is smallest. Mark inMST[1] = true. totalCost += 4 = 4. Update neighbors:

minDist[2] = min(13, dist(1,2)) = min(13, 9) = 9
minDist[3] = min(7, dist(1,3)) = min(7, 3) = 3
minDist[4] = min(7, dist(1,4)) = min(7, 7) = 7
Now minDist = [0, 4, 9, 3, 7].

Step 4 — Pick vertex 3 (minDist=3): Scan for minimum: minDist[3]=3 is smallest. Mark inMST[3] = true. totalCost += 3 = 7. Update neighbors:

minDist[2] = min(9, dist(3,2)) = min(9, 10) = 9
minDist[4] = min(7, dist(3,4)) = min(7, 4) = 4
Now minDist = [0, 4, 9, 3, 4].

Step 5 — Pick vertex 4 (minDist=4): Scan for minimum: minDist[4]=4 is smallest. Mark inMST[4] = true. totalCost += 4 = 11. Update neighbors:

minDist[2] = min(9, dist(4,2)) = min(9, 14) = 9
Now minDist = [0, 4, 9, 3, 4].

Step 6 — Pick vertex 2 (minDist=9): Only unvisited vertex left. Mark inMST[2] = true. totalCost += 9 = 20.

Step 7 — Result: All vertices in MST. Return totalCost = 20.

Prim's Algorithm — Growing MST from a Single Vertex — Watch how Prim's algorithm grows the MST one vertex at a time, always connecting the nearest unvisited point to the existing tree without ever sorting edges.

Algorithm

Initialize an array minDist of size n, with minDist[0] = 0 and all others set to infinity. This represents the minimum cost to connect each vertex to the MST.
Initialize a boolean array inMST of size n, all set to false.
Initialize totalCost = 0.
Repeat n times:
a. Find minimum: Scan minDist to find the unvisited vertex u with the smallest value.
b. Add to MST: Set inMST[u] = true and add minDist[u] to totalCost.
c. Update neighbors: For every unvisited vertex v, compute dist = |points[u][0] - points[v][0]| + |points[u][1] - points[v][1]|. If dist < minDist[v], update minDist[v] = dist.
Return totalCost.

Code

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        vector<int> minDist(n, INT_MAX);
        vector<bool> inMST(n, false);
        minDist[0] = 0;
        int totalCost = 0;

        for (int i = 0; i < n; i++) {
            // Find the unvisited vertex with minimum minDist
            int u = -1;
            for (int v = 0; v < n; v++) {
                if (!inMST[v] && (u == -1 || minDist[v] < minDist[u])) {
                    u = v;
                }
            }

            inMST[u] = true;
            totalCost += minDist[u];

            // Update minDist for all unvisited neighbors
            for (int v = 0; v < n; v++) {
                if (!inMST[v]) {
                    int dist = abs(points[u][0] - points[v][0])
                             + abs(points[u][1] - points[v][1]);
                    minDist[v] = min(minDist[v], dist);
                }
            }
        }

        return totalCost;
    }
};

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        min_dist = [float('inf')] * n
        in_mst = [False] * n
        min_dist[0] = 0
        total_cost = 0

        for _ in range(n):
            # Find the unvisited vertex with minimum min_dist
            u = -1
            for v in range(n):
                if not in_mst[v] and (u == -1 or min_dist[v] < min_dist[u]):
                    u = v

            in_mst[u] = True
            total_cost += min_dist[u]

            # Update min_dist for all unvisited neighbors
            for v in range(n):
                if not in_mst[v]:
                    dist = (abs(points[u][0] - points[v][0])
                          + abs(points[u][1] - points[v][1]))
                    min_dist[v] = min(min_dist[v], dist)

        return total_cost

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        int[] minDist = new int[n];
        boolean[] inMST = new boolean[n];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[0] = 0;
        int totalCost = 0;

        for (int i = 0; i < n; i++) {
            // Find the unvisited vertex with minimum minDist
            int u = -1;
            for (int v = 0; v < n; v++) {
                if (!inMST[v] && (u == -1 || minDist[v] < minDist[u])) {
                    u = v;
                }
            }

            inMST[u] = true;
            totalCost += minDist[u];

            // Update minDist for all unvisited neighbors
            for (int v = 0; v < n; v++) {
                if (!inMST[v]) {
                    int dist = Math.abs(points[u][0] - points[v][0])
                             + Math.abs(points[u][1] - points[v][1]);
                    minDist[v] = Math.min(minDist[v], dist);
                }
            }
        }

        return totalCost;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times. In each iteration, finding the minimum takes O(n) and updating neighbors also takes O(n). Total: n × O(n) = O(n²). This is optimal for a complete graph because just reading all edge weights already takes O(n²) time.

Space Complexity: O(n)

We use two arrays of size n: minDist and inMST. Unlike Kruskal's approach, we never store the full edge list, saving O(n²) space.