Problem statement

An undirected graph has n nodes labelled 0 to n - 1. Each edges[i] = [u, v, time] is an edge between u and v that disappears at moment time: once the clock reads t, every edge with time <= t is gone.

Return the smallest integer t >= 0 such that, after removing every edge with time <= t, the graph has at least k connected components.

Example 1

Input: n = 4, edges = [[0,1,3],[1,2,7],[2,3,5]], k = 2
Output: 3
Explanation: At t = 3 only the edges timed 7 and 5 remain: components {0} and {1,2,3}. At any t < 3 all three edges survive and the graph is one component.

Example 2

Input: n = 3, edges = [[0,1,2],[1,2,4]], k = 3
Output: 4
Explanation: Three components need every edge gone, which first happens at t = 4.

Example 3

Input: n = 3, edges = [[0,2,5]], k = 2
Output: 0
Explanation: Node 1 is already alone, so there are two components at t = 0.

Constraints

• 1 <= n <= 10^5
• 0 <= edges.length <= 10^5
• edges[i] = [u, v, time]
• 0 <= u, v < n, u != v
• 1 <= time <= 10^9
• 1 <= k <= n
• there are no duplicate edges

Hints for Minimum Time for K Connected Components

1. Hint 1

   The number of components only grows as t grows, so the answer is monotone — binary search over t would work.

2. Hint 2

   Look at it backwards: start from an empty graph and add edges from the latest-disappearing to the earliest.

3. Hint 3

   With union-find, the first edge whose union would leave fewer than k components cannot survive — its time is the answer. If no such edge exists, the answer is 0.

How to solve Minimum Time for K Connected Components

Removing edges with time <= t keeps exactly the edges with time > t. Adding edges in decreasing order of time builds those graphs from large t down to small, and union-find counts components as we go.

Approach

1. Sort the edges by time, largest first.
2. Start with n singleton components.
3. For each edge [u, v, time]: if u and v are already joined, skip it. Otherwise, if merging would leave components - 1 < k, return time. Else merge and decrement the count.
4. If every edge was added without dropping below k, return 0.

Why it works

When the loop returns time = T, every edge with a larger time is already in and the graph still has at least k components, so t = T (which removes this edge and everything not later) works. Any t < T keeps this edge as well, and the edges already added, so the components fall below k — merging only lowers the count further.

Complexity

• Time — O(m log m + m α(n))
• Space — O(n + m)

Pitfalls

• Edges with the same time disappear together; returning that shared time is still correct because the answer is the edge's time, not one less.
• The answer can be 0 — when the graph already has k or more components.
• An edge between two nodes already connected never changes the count, so it must not trigger a return.

Reference solution

Python

from typing import List

def minTime(n: int, edges: List[List[int]], k: int) -> int:
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    comps = n
    for u, v, t in sorted(edges, key=lambda e: -e[2]):
        a, b = find(u), find(v)
        if a == b:
            continue
        if comps - 1 < k:
            return t
        parent[a] = b
        comps -= 1
    return 0

Java

static int mtFind(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

public static int minTime(int n, int[][] edges, int k) {
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    int[][] sorted = edges.clone();
    Arrays.sort(sorted, (p, q) -> Integer.compare(q[2], p[2]));
    int comps = n;
    for (int[] e : sorted) {
        int a = mtFind(parent, e[0]), b = mtFind(parent, e[1]);
        if (a == b) continue;
        if (comps - 1 < k) return e[2];
        parent[a] = b;
        comps--;
    }
    return 0;
}

C++

static int mtFind(vector<int>& parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

int minTime(int n, vector<vector<int>>& edges, int k) {
    vector<int> parent(n);
    for (int i = 0; i < n; i++) parent[i] = i;
    vector<vector<int>> sorted = edges;
    sort(sorted.begin(), sorted.end(), [](const vector<int>& p, const vector<int>& q) { return p[2] > q[2]; });
    int comps = n;
    for (auto& e : sorted) {
        int a = mtFind(parent, e[0]), b = mtFind(parent, e[1]);
        if (a == b) continue;
        if (comps - 1 < k) return e[2];
        parent[a] = b;
        comps--;
    }
    return 0;
}

JavaScript

var minTime = function(n, edges, k) {
    var parent = [];
    for (var i = 0; i < n; i++) parent.push(i);
    var find = function(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    var sorted = edges.slice().sort(function(p, q) { return q[2] - p[2]; });
    var comps = n;
    for (var e = 0; e < sorted.length; e++) {
        var a = find(sorted[e][0]), b = find(sorted[e][1]);
        if (a === b) continue;
        if (comps - 1 < k) return sorted[e][2];
        parent[a] = b;
        comps--;
    }
    return 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More sorting problems

• Implement Router Medium
• Longest Uploaded Prefix Medium
• Range Frequency Queries Medium
• Tweet Counts Per Frequency Medium
• Snapshot Array Medium
• Time Based Key-Value Store Medium