LeetCode Problem 3608

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

Solution

Minimum Time for K Connected Components

Problem Understanding

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

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

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

Another way to think about the problem is that 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 non-decreasing function of time.

The input consists of:

• n, the number of vertices labeled from 0 to n - 1
• edges, where each edge is represented as [u, v, time]
• k, the minimum number of connected components we want to achieve

The output is the minimum time at which the graph has at least k connected components.

The constraints are important:

• n <= 100000
• edges.length <= 100000
• Removal times can be as large as 10^9

These limits immediately rule out algorithms that repeatedly rebuild the graph or run graph traversals for every possible time value.

Several edge cases deserve attention:

• The graph may already contain at least k connected components before any edge is removed. In that case the answer is 0.
• The graph may contain no edges at all.
• The graph may already be disconnected.
• Removal times are very large, so we cannot iterate through all possible times.
• Multiple connected components may appear only after many edge removals.

The problem guarantees there are no duplicate edges.

Approaches

Brute Force

A straightforward approach is to simulate every relevant time value.

For each candidate time t:

1. Remove all edges with time <= t.
2. Build the remaining graph.
3. Run DFS or BFS to count connected components.
4. Check whether the count is at least k.

This is correct because it directly follows the problem definition.

Unfortunately, it is far too slow. There can be up to 100000 distinct edge times. Rebuilding the graph and recounting connected components for each candidate time would require roughly:

$$O(m \cdot (n+m))$$

which is completely infeasible for the given constraints.

Key Insight

Instead of thinking about removed edges, think about the edges that remain.

At time t, an edge remains if:

$$time_i > t$$

If we know a candidate time t, we can determine the number of connected components by considering only edges whose removal times are greater than t.

A Union-Find structure can efficiently count connected components among those remaining edges.

The crucial observation is monotonicity:

• As t increases, more edges disappear.
• Therefore the number of connected components never decreases.
• Once we reach at least k connected components, every larger time will also satisfy the condition.

This monotonic property makes binary search possible.

For a given time t:

• Keep all edges with time > t.
• Use Union-Find to connect their endpoints.
• Count resulting connected components.
• Check whether the count is at least k.

Then binary search for the smallest valid time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m(n+m))	O(n+m)	Rebuild and traverse graph for every candidate time
Optimal	O(m log m + m log U)	O(n)	Binary search on time with Union-Find checks

Here:

• m = edges.length
• U = max(timei)

Since log U ≤ 30, the optimal solution is easily fast enough.

Algorithm Walkthrough

1. First 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. Using Union-Find on all edges gives the initial component count. If this count is already at least k, return 0 immediately. 2. Determine the binary search range.

The smallest possible answer is 1, and the largest possible answer is the maximum edge removal time present in the input. 3. Define a helper function enough(t).

This function determines whether the graph has at least k connected components after all edges with time <= t have been removed. 4. Inside enough(t), create a fresh Union-Find structure.

Initially every node is its own component. 5. Process all edges.

For every edge [u, v, time]:

• If time > t, the edge still exists.
• Union u and v.

6. After processing all remaining edges, the Union-Find component count equals the number of connected components in the graph at time t.
7. Return whether the component count is at least k.
8. Perform binary search.

If enough(mid) is true, store mid as a potential answer and continue searching the left half because we want the minimum valid time.

Otherwise, search the right half. 9. When binary search finishes, return the stored answer.

Why it works

Let f(t) be the number of connected components after removing all edges with removal time at most t.

As t increases, edges are only removed, never added. Removing edges cannot merge connected components, so f(t) is monotonic non-decreasing.

The helper function checks exactly whether f(t) >= k. Because this predicate is monotonic, binary search correctly finds the smallest time where it becomes true. Union-Find accurately computes connected components among the remaining edges, so every feasibility check is correct.

Python Solution

from typing import List

class Solution:
    def minTime(self, n: int, edges: List[List[int]], k: int) -> int:
        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:
                if self.parent[x] != x:
                    self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

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

                if ra == rb:
                    return False

                if self.rank[ra] < self.rank[rb]:
                    ra, rb = rb, ra

                self.parent[rb] = ra

                if self.rank[ra] == self.rank[rb]:
                    self.rank[ra] += 1

                self.components -= 1
                return True

        # Check time 0
        uf0 = UnionFind(n)
        for u, v, _ in edges:
            uf0.union(u, v)

        if uf0.components >= k:
            return 0

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

        def enough(t: int) -> bool:
            uf = UnionFind(n)

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

            return uf.components >= k

        left = 1
        right = max_time
        answer = max_time

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

            if enough(mid):
                answer = mid
                right = mid - 1
            else:
                left = mid + 1

        return answer

The implementation begins with a standard Union-Find data structure using path compression and union by rank. The components field tracks the current number of connected components directly, eliminating the need for an additional counting pass.

The first Union-Find instance computes the component count at time 0, when all edges are still present. If this already satisfies the requirement, the answer is immediately 0.

The helper function enough(t) rebuilds the graph state corresponding to time t. Instead of explicitly removing edges, it simply keeps edges whose removal time is greater than t. After processing those edges, the Union-Find component count tells us how many connected components remain.

Binary search then exploits the monotonic nature of the condition. Whenever a time is valid, the algorithm continues searching for a smaller valid time. Otherwise it searches larger times.

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 {
	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x])
	}
	return uf.parent[x]
}

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

	if ra == rb {
		return false
	}

	if uf.rank[ra] < uf.rank[rb] {
		ra, rb = rb, ra
	}

	uf.parent[rb] = ra

	if uf.rank[ra] == uf.rank[rb] {
		uf.rank[ra]++
	}

	uf.components--
	return true
}

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

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

	if uf0.components >= k {
		return 0
	}

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

	enough := func(t int) bool {
		uf := NewUnionFind(n)

		for _, edge := range edges {
			u, v, time := edge[0], edge[1], edge[2]

			if time > t {
				uf.Union(u, v)
			}
		}

		return uf.components >= k
	}

	left, right := 1, maxTime
	answer := maxTime

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

		if enough(mid) {
			answer = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}

	return answer
}

The Go implementation mirrors the Python solution closely. Slices are used for the parent and rank arrays. Integer overflow is not a concern because edge times are at most 10^9, but the binary search midpoint is still computed using left + (right-left)/2, which is the conventional safe approach in Go.

Worked Examples

Example 1

Input:

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

Initial graph:

Edge	Removal Time
(0,1)	3

Time 0 check:

Remaining Edges	Components
(0,1)	1

1 < 2, so continue.

Binary search:

t	Remaining Edges	Components	Valid?
2	(0,1)	1	No
3	none	2	Yes

Answer = 3.

Example 2

Input:

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

Time 0:

Remaining Edges	Components
(0,1), (1,2)	1

Binary search:

t	Remaining Edges	Components
2	(1,2)	2
3	(1,2)	2
4	none	3

First valid time is 4.

Example 3

Input:

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

Time 0:

Remaining Edges	Components
(0,2)	2

Since components already equal k, return 0.

No binary search is required.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m log U)	Each binary search step scans all edges once
Space	O(n)	Union-Find arrays store parent and rank information

Let m be the number of edges and U be the maximum removal time. The binary search performs at most log U iterations, which is at most about 30 because U ≤ 10^9. Each iteration rebuilds a Union-Find structure and processes every edge once. Therefore the total running time is O(m log U). The Union-Find structure stores only arrays of size n, giving O(n) auxiliary space.

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 fully disconnected

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

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

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

assert sol.minTime(
    5,
    [[0, 1, 1000000000]],
    5
) == 1000000000  # Large timestamp

assert sol.minTime(
    5,
    [[0, 1, 2], [1, 2, 2], [3, 4, 5]],
    3
) == 2  # Multiple removals at same time

Test	Why
Example 1	Basic connected graph
Example 2	Multiple removal stages
Example 3	Already satisfies requirement
Single node	Smallest possible graph
No edges	Maximum initial component count
Two disconnected pairs	Initially disconnected graph
Chain graph	Requires removing every edge
Same timestamp edges	Simultaneous removals
Large timestamp	Tests upper time bound
Multiple equal times	Verifies binary search around duplicate times

Edge Cases

Graph Already Has Enough Components

A common mistake is immediately starting binary search without checking the initial graph state. The graph may already contain at least k connected components before any edge is removed. In that situation the correct answer is 0. The implementation explicitly computes the component count at time 0 and returns immediately when the condition is already satisfied.

Graph With No Edges

When edges is empty, every vertex is its own connected component. A naive implementation might attempt to binary search over edge times and fail because there is no maximum edge time. The early time-0 check handles this naturally because the graph already contains n connected components.

Multiple Edges Sharing the Same Removal Time

Several edges may disappear simultaneously. A buggy implementation might incorrectly process them one at a time and return an intermediate time that never actually exists. The solution avoids this issue by defining the graph at time t exactly as all edges satisfying time > t. Every edge with the same removal time is removed together, matching the problem statement precisely.

Initially Disconnected Graph

The graph is not guaranteed to be connected. Some solutions incorrectly assume a single connected component at the start. The Union-Find initialization computes the actual component count from the provided graph structure, so disconnected inputs are handled correctly.

Large Time Values

Removal times can be as large as 10^9. Iterating through time values directly would be impossible. Binary search relies only on the ordering of times, not their magnitude, which keeps the algorithm efficient regardless of how large the timestamps become.