Difficulty: 🟡 Medium
Topics: Binary Search, Union-Find, Graph Theory, Sorting

Solution

LeetCode 3608 - Minimum Time for K Connected Components

Problem Understanding

We are given an undirected graph with n vertices and a list of edges. Each edge has a removal time timei.

The graph evolves over time. At time t, every edge whose removal time satisfies timei <= t has already been removed. All remaining edges are those with timei > t.

Our goal is to find the smallest time t such that the graph contains at least k connected components.

Another way to view the problem is:

At time 0, no edges have been removed.
As time increases, more and more edges disappear.
Removing edges can never decrease the number of connected components.
Therefore, the number of connected components is a monotonic non-decreasing function of time.
We need the earliest time when the component count reaches or exceeds k.

The input consists of:

n, the number of vertices.
edges, where each entry [u, v, time] describes an undirected edge that disappears at time.
k, the required minimum number of connected components.

The output is a single integer, the minimum time satisfying the condition.

The constraints are large:

Up to 10^5 vertices.
Up to 10^5 edges.
Edge removal times up to 10^9.

These limits immediately rule out any solution that repeatedly rebuilds the graph for every possible time value.

Several edge cases are important:

The graph may already have at least k connected components at time 0, in which case the answer is 0.
The graph may contain no edges at all.
k may equal 1, meaning the answer is always 0 because every graph has at least one connected component.
The graph may already be disconnected before any removals occur.
Edge times can be very large, so iterating through all time values is impossible.

Approaches

Brute Force

A straightforward approach is to test every candidate time.

For a chosen time t:

Remove all edges with time <= t.
Build the remaining graph.
Run DFS/BFS or Union-Find to count connected components.
Check whether the count is at least k.

The answer is the first time where the condition becomes true.

This is correct because it directly simulates the definition of the problem.

Unfortunately, it is far too slow. The time values can be as large as 10^9, and even if we only test distinct edge times, we could still perform up to 10^5 graph reconstructions. Each reconstruction costs O(n + m).

Key Insight

The crucial observation is monotonicity.

Let:

f(t) = number of connected components after removing all edges with time <= t.

As t increases:

More edges disappear.
Existing connected components may split.
Components can never merge.

Therefore:

f(t) is non-decreasing.

This monotonic property makes binary search possible.

For a fixed time t, we can determine the component count by keeping only edges with:

time > t

and using Union-Find to connect their endpoints.

If the resulting component count is at least k, then every larger time will also satisfy the condition.

Thus we can binary search for the smallest valid time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m(n+m)) or worse	O(n+m)	Rebuilds graph for many candidate times
Optimal	O(m log M)	O(n)	Binary search on time, Union-Find for connectivity

Here M is the maximum edge removal time.

Algorithm Walkthrough

Optimal Algorithm

Compute the number of connected components at time 0.

At time 0, no edge has been removed because all removal times are at least 1. Use Union-Find over all edges and count the resulting components. 2. If the graph already has at least k connected components, return 0.

Since we need the minimum time, no waiting is necessary. 3. Let max_time be the largest removal time among all edges. 4. Define a helper function can(t).

This function determines whether removing all edges with time <= t leaves at least k connected components. 5. Inside can(t):

Create a fresh Union-Find with n components.
Iterate through every edge.
If time > t, the edge still exists, so union its endpoints.
Ignore edges with time <= t because they have been removed.
After processing all surviving edges, count components.
Return whether the component count is at least k.

Perform binary search on the answer range [1, max_time].

Let mid = (left + right) // 2.
If can(mid) is true, the answer is at most mid, so move left.
Otherwise, move right.

When binary search finishes, return the smallest valid time.

Why it works

For any time t, the graph consists exactly of edges whose removal times are greater than t. The helper function computes the connected components of that graph using Union-Find.

The number of connected components cannot decrease as time increases because increasing time only removes more edges. Therefore the predicate

"the graph has at least k connected components"

is monotonic. Binary search correctly finds the first time where the predicate becomes true. Since every check computes the exact component count, the returned time is precisely the minimum valid time.

Python Solution

from typing import List

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> bool:
        pa = self.find(a)
        pb = self.find(b)

        if pa == pb:
            return False

        if self.rank[pa] < self.rank[pb]:
            pa, pb = pb, pa

        self.parent[pb] = pa

        if self.rank[pa] == self.rank[pb]:
            self.rank[pa] += 1

        self.components -= 1
        return True

class Solution:
    def minTime(self, n: int, edges: List[List[int]], k: int) -> int:
        uf = UnionFind(n)

        for u, v, _ in edges:
            uf.union(u, v)

        if uf.components >= k:
            return 0

        max_time = max(time for _, _, time in edges)

        def can(t: int) -> bool:
            dsu = UnionFind(n)

            for u, v, time in edges:
                if time > t:
                    dsu.union(u, v)

            return dsu.components >= k

        left, right = 1, max_time

        while left < right:
            mid = (left + right) // 2

            if can(mid):
                right = mid
            else:
                left = mid + 1

        return left

The implementation begins by computing the connected components at time 0. If the graph already satisfies the requirement, it immediately returns 0.

The can() function reconstructs the graph state at a particular time by keeping only edges whose removal time is larger than t. Union-Find efficiently merges connected vertices and tracks the number of remaining components.

Because the predicate is monotonic, a standard binary search finds the smallest valid time. Each midpoint evaluation uses a fresh Union-Find structure and processes all edges once.

Go Solution

package main

type UnionFind struct {
	parent     []int
	rank       []int
	components int
}

func NewUnionFind(n int) *UnionFind {
	parent := make([]int, n)
	rank := make([]int, n)

	for i := 0; i < n; i++ {
		parent[i] = i
	}

	return &UnionFind{
		parent:     parent,
		rank:       rank,
		components: n,
	}
}

func (uf *UnionFind) Find(x int) int {
	for uf.parent[x] != x {
		uf.parent[x] = uf.parent[uf.parent[x]]
		x = uf.parent[x]
	}
	return x
}

func (uf *UnionFind) Union(a, b int) bool {
	pa := uf.Find(a)
	pb := uf.Find(b)

	if pa == pb {
		return false
	}

	if uf.rank[pa] < uf.rank[pb] {
		pa, pb = pb, pa
	}

	uf.parent[pb] = pa

	if uf.rank[pa] == uf.rank[pb] {
		uf.rank[pa]++
	}

	uf.components--
	return true
}

func minTime(n int, edges [][]int, k int) int {
	uf := NewUnionFind(n)

	for _, e := range edges {
		uf.Union(e[0], e[1])
	}

	if uf.components >= k {
		return 0
	}

	maxTime := 0
	for _, e := range edges {
		if e[2] > maxTime {
			maxTime = e[2]
		}
	}

	can := func(t int) bool {
		dsu := NewUnionFind(n)

		for _, e := range edges {
			if e[2] > t {
				dsu.Union(e[0], e[1])
			}
		}

		return dsu.components >= k
	}

	left, right := 1, maxTime

	for left < right {
		mid := left + (right-left)/2

		if can(mid) {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return left
}

The Go implementation mirrors the Python solution closely. Slices are used for the parent and rank arrays, and component counting is maintained directly inside the Union-Find structure. Integer overflow is not a concern because all values fit comfortably within Go's int range under the given constraints.

Worked Examples

Example 1

Input:

n = 2
edges = [[0,1,3]]
k = 2

At time 0:

Remaining Edges	Components
(0,1)	1

Not enough, so continue.

Binary search range:

[1, 3]

Check t = 2.

Edge	Survives?
time=3	Yes

Components = 1.

1 < 2

Move right.

Check t = 3.

Edge	Survives?
time=3	No

Components = 2.

2 >= 2

Answer = 3.

Example 2

Input:

n = 3
edges = [[0,1,2],[1,2,4]]
k = 3

At time 0:

0-1-2

Components = 1.

Check t = 2.

Remaining edge:

1-2

Components:

{0}, {1,2}

Count = 2.

Not enough.

Check t = 4.

No edges remain.

Components:

{0}, {1}, {2}

Count = 3.

Answer = 4.

Example 3

Input:

n = 3
edges = [[0,2,5]]
k = 2

At time 0:

Components are:

{0,2}, {1}

Count = 2.

Since the graph already contains at least k components, return:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m log M)	Binary search performs O(log M) checks, each processes all edges
Space	O(n)	Union-Find arrays store parent and rank information

Here:

m = len(edges)
M = max(edge removal time)

Each binary search iteration constructs a Union-Find and scans all edges once. Since log2(10^9) is about 30, the number of iterations is small.

Test Cases

sol = Solution()

assert sol.minTime(2, [[0, 1, 3]], 2) == 3  # example 1

assert sol.minTime(
    3,
    [[0, 1, 2], [1, 2, 4]],
    3
) == 4  # example 2

assert sol.minTime(
    3,
    [[0, 2, 5]],
    2
) == 0  # example 3

assert sol.minTime(
    1,
    [],
    1
) == 0  # single node

assert sol.minTime(
    5,
    [],
    5
) == 0  # already disconnected

assert sol.minTime(
    4,
    [[0, 1, 10], [2, 3, 20]],
    3
) == 10  # first edge removal creates third component

assert sol.minTime(
    4,
    [[0, 1, 5], [1, 2, 5], [2, 3, 5]],
    4
) == 5  # all edges removed simultaneously

assert sol.minTime(
    5,
    [[0, 1, 1], [1, 2, 2], [2, 3, 3], [3, 4, 4]],
    3
) == 3  # gradual disconnection

assert sol.minTime(
    6,
    [[0, 1, 1000000000]],
    6
) == 1000000000  # maximum time value

assert sol.minTime(
    4,
    [[0, 1, 3], [2, 3, 7]],
    2
) == 0  # already has two components

Test Summary

Test	Why
Example 1	Single edge removal
Example 2	Chain requiring multiple removals
Example 3	Already satisfies requirement
Single node	Minimum possible graph
No edges	Maximum initial components
Two disconnected pairs	Intermediate answer
Equal removal times	Multiple edges disappear together
Increasing removal times	Gradual component growth
Time = 1e9	Upper constraint boundary
Initially disconnected graph	Immediate answer of 0

Edge Cases

One important edge case occurs when the graph already contains at least k connected components before any removals happen. A binary search that assumes some positive answer could incorrectly return a positive time. The implementation explicitly computes the component count at time 0 and returns 0 immediately when the condition is already satisfied.

Another important case is a graph with no edges. In this situation every vertex forms its own connected component from the beginning. The solution handles this naturally because the initial Union-Find contains n components and no unions are performed. If n >= k, the answer is correctly 0.

A third edge case occurs when many edges share the same removal time. The problem removes all edges with time <= t, meaning every edge with that timestamp disappears simultaneously. The binary search predicate uses the exact condition time > t for surviving edges, ensuring that all equal-time edges are treated consistently and preventing off-by-one errors.

A final subtle case is when k = 1. Every graph with at least one vertex already has at least one connected component. The initial component count check immediately returns 0, which is the correct minimum time.