Minimum Time for K Connected Components solution and explanation
4 more videos on this problem
Leetcode 3608 | Minimum time for k connected components | Leetcode weekly context 457CodeWithMeGuys · 8:17 · 449 views
3608. Minimum Time for K Connected Components (Leetcode Medium)Programming Live with Larry · 24:13 · 348 views
LeetCode 3608. Minimum Time for K Connected Components | Binary Search | Graph | DFS | MediumLeet's Code · 30:19 · 336 views
3608. Minimum Time for K Connected Components | DSU + Binary search | weekly contest 457 - Q3codingX krishna · 49:29 · 222 views
Minimum Time for K Connected Components | Leetcode 3608 Java Solution + IntuitionExpertFunda · 27:30 · 200 views
The problem
You are given an integer n and an undirected graph with n nodes labeled from 0 to n - 1. This is represented by a 2D array edges, where edges[i] = [ui, vi, timei] indicates an undirected edge between nodes ui and vi that can be removed at timei.
You are also given an integer k.
Initially, the graph may be connected or disconnected. Your task is to find the minimum time t such that after removing all edges with time <= t, the graph contains at least k connected components.
Return the minimum time t.
A connected component is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.
Example 1:
Input: n = 2, edges = [[0,1,3]], k = 2
Output: 3
Explanation:
- Initially, there is one connected component
{0, 1}. - At
time = 1or2, the graph remains unchanged. - At
time = 3, edge[0, 1]is removed, resulting ink = 2connected components{0},{1}. Thus, the answer is 3.
Example 2:
Input: n = 3, edges = [[0,1,2],[1,2,4]], k = 3
Output: 4
Explanation:
- Initially, there is one connected component
{0, 1, 2}. - At
time = 2, edge[0, 1]is removed, resulting in two connected components{0},{1, 2}. - At
time = 4, edge[1, 2]is removed, resulting ink = 3connected components{0},{1},{2}. Thus, the answer is 4.
Example 3:
Input: n = 3, edges = [[0,2,5]], k = 2
Output: 0
Explanation:
- Since there are already
k = 2disconnected components{1},{0, 2}, no edge removal is needed. Thus, the answer is 0.
Constraints:
1 <= n <= 1050 <= edges.length <= 105edges[i] = [ui, vi, timei]0 <= ui, vi < nui != vi1 <= timei <= 1091 <= k <= n- There are no duplicate edges.
Approach overview
Problem Overview: You are given connections between nodes that become available at specific times. The goal is to determine the earliest time when the graph forms k or fewer connected components. Edges effectively “activate” over time, so the task becomes identifying the minimum timestamp where enough edges exist to merge components down to k.
Approach 1: Sort Edges + Union-Find Sweep (O(E log E) time, O(N) space)
Sort all edges by their activation time. Start with n components where every node is its own set. Process edges in increasing time order and merge endpoints using a Disjoint Set Union structure. Each successful union reduces the component count by one. As soon as the number of components becomes <= k, the current edge time is the answer.
The key idea mirrors Kruskal’s algorithm: edges added earlier merge components earlier. Union-Find keeps merges efficient with path compression and union by rank. This approach performs a single pass after sorting and works well when the earliest valid time occurs early in the edge list. See related concepts in Union Find and Graph algorithms.
Approach 2: Binary Search on Time + Union-Find Check (O(E log E + E log T) time, O(N) space)
Instead of scanning edges once, treat time as the search space. Sort edges by time and perform Binary Search over the possible timestamps. For a candidate time t, build components using only edges whose time is <= t. Count the resulting components with Union-Find.
If the component count is <= k, the time works and you search earlier times. Otherwise, you need more edges, so search later times. The feasibility check is monotonic: once a time produces at most k components, all larger times will also satisfy the condition. This monotonic property makes binary search valid.
This approach is useful when the time range is large or when the solution pattern matches “minimum time to satisfy a condition.” Each check rebuilds connectivity using Union-Find, keeping operations close to constant time due to path compression.
Recommended for interviews: The Union-Find sweep after sorting edges is the cleanest solution and easiest to reason about. It directly tracks component merges and stops once the count reaches k. Binary search with Union-Find demonstrates stronger algorithmic pattern recognition and is commonly expected when problems involve “minimum time” or monotonic feasibility checks.
Solution
We can sort the edges by time in ascending order, then starting from the edge with the largest time, add edges to the graph one by one, while using a union-find data structure to maintain the number of connected components in the current graph. When the number of connected components is less than k, the current time is the minimum time we are looking for.
The time complexity is O(n times \alpha(n)), and the space complexity is O(n), where \alpha is the inverse Ackermann function.
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.size = [1] * n
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.size[pa] > self.size[pb]:
self.p[pb] = pa
self.size[pa] += self.size[pb]
else:
self.p[pa] = pb
self.size[pb] += self.size[pa]
return True
class Solution:
def minTime(self, n: int, edges: List[List[int]], k: int) -> int:
edges.sort(key=lambda x: x[2])
uf = UnionFind(n)
cnt = n
for u, v, t in edges[::-1]:
if uf.union(u, v):
cnt -= 1
if cnt < k:
return t
return 0class UnionFind {
private int[] p;
private int[] size;
public UnionFind(int n) {
p = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
p[i] = i;
size[i] = 1;
}
}
public int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
public boolean union(int a, int b) {
int pa = find(a);
int pb = find(b);
if (pa == pb) {
return false;
}
if (size[pa] > size[pb]) {
p[pb] = pa;
size[pa] += size[pb];
} else {
p[pa] = pb;
size[pb] += size[pa];
}
return true;
}
}
class Solution {
public int minTime(int n, int[][] edges, int k) {
Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
UnionFind uf = new UnionFind(n);
int cnt = n;
for (int i = edges.length - 1; i >= 0; i--) {
int u = edges[i][0];
int v = edges[i][1];
int t = edges[i][2];
if (uf.union(u, v)) {
if (--cnt < k) {
return t;
}
}
}
return 0;
}
}class UnionFind {
public:
vector<int> p;
vector<int> size;
UnionFind(int n) {
p.resize(n);
size.resize(n, 1);
for (int i = 0; i < n; i++) {
p[i] = i;
}
}
int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
bool unite(int a, int b) {
int pa = find(a);
int pb = find(b);
if (pa == pb) {
return false;
}
if (size[pa] > size[pb]) {
p[pb] = pa;
size[pa] += size[pb];
} else {
p[pa] = pb;
size[pb] += size[pa];
}
return true;
}
};
class Solution {
public:
int minTime(int n, vector<vector<int>>& edges, int k) {
sort(edges.begin(), edges.end(), [](const vector<int>& a, const vector<int>& b) {
return a[2] < b[2];
});
UnionFind uf(n);
int cnt = n;
for (int i = edges.size() - 1; i >= 0; i--) {
int u = edges[i][0];
int v = edges[i][1];
int t = edges[i][2];
if (uf.unite(u, v)) {
cnt--;
if (cnt < k) {
return t;
}
}
}
return 0;
}
};class UnionFind {
p: number[];
size: number[];
constructor(n: number) {
this.p = Array.from({ length: n }, (_, i) => i);
this.size = Array(n).fill(1);
}
find(x: number): number {
if (this.p[x] !== x) {
this.p[x] = this.find(this.p[x]);
}
return this.p[x];
}
union(a: number, b: number): boolean {
const pa = this.find(a);
const pb = this.find(b);
if (pa === pb) return false;
if (this.size[pa] > this.size[pb]) {
this.p[pb] = pa;
this.size[pa] += this.size[pb];
} else {
this.p[pa] = pb;
this.size[pb] += this.size[pa];
}
return true;
}
}
function minTime(n: number, edges: number[][], k: number): number {
edges.sort((a, b) => a[2] - b[2]);
const uf = new UnionFind(n);
let cnt = n;
for (let i = edges.length - 1; i >= 0; i--) {
const [u, v, t] = edges[i];
if (uf.union(u, v)) {
if (--cnt < k) {
return t;
}
}
}
return 0;
}type UnionFind struct {
p []int
size []int
}
func NewUnionFind(n int) *UnionFind {
uf := &UnionFind{
p: make([]int, n),
size: make([]int, n),
}
for i := 0; i < n; i++ {
uf.p[i] = i
uf.size[i] = 1
}
return uf
}
func (uf *UnionFind) find(x int) int {
if uf.p[x] != x {
uf.p[x] = uf.find(uf.p[x])
}
return uf.p[x]
}
func (uf *UnionFind) union(a, b int) bool {
pa := uf.find(a)
pb := uf.find(b)
if pa == pb {
return false
}
if uf.size[pa] > uf.size[pb] {
uf.p[pb] = pa
uf.size[pa] += uf.size[pb]
} else {
uf.p[pa] = pb
uf.size[pb] += uf.size[pa]
}
return true
}
func minTime(n int, edges [][]int, k int) int {
sort.Slice(edges, func(i, j int) bool {
return edges[i][2] < edges[j][2]
})
uf := NewUnionFind(n)
cnt := n
for i := len(edges) - 1; i >= 0; i-- {
u := edges[i][0]
v := edges[i][1]
t := edges[i][2]
if uf.union(u, v) {
cnt--
if cnt < k {
return t
}
}
}
return 0
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort Edges + Union-Find Sweep | O(E log E) | O(N) | Best general solution when edges have timestamps and you only need the earliest merge point |
| Binary Search on Time + Union-Find | O(E log E + E log T) | O(N) | Useful when solving minimum/earliest time feasibility problems with monotonic conditions |
Frequently asked questions
Is Minimum Time for K Connected Components easy or hard?
This problem is typically classified as Medium difficulty. The challenge is recognizing that the component count decreases monotonically as edges are added, which enables a Union-Find sweep or a binary search feasibility check.
Minimum Time for K Connected Components Python/Java solution
Most implementations use Union-Find with path compression. The algorithm sorts edges by time and merges nodes while tracking the number of components. The same logic translates cleanly across Python, Java, C++, Go, and TypeScript.
How to solve Minimum Time for K Connected Components in O(E log E)?
Sort all edges by their activation time. Initialize Union-Find with n separate components. Iterate through edges and union their endpoints; every successful union reduces the component count. When the number of components becomes less than or equal to k, return the current time.
What is the best approach for Minimum Time for K Connected Components?
The most practical solution sorts edges by time and processes them using Union-Find. Each union reduces the number of connected components. Once the component count becomes less than or equal to k, the current edge time is the answer. The approach runs in O(E log E) time due to sorting and near O(1) amortized union operations.
Is Minimum Time for K Connected Components asked at Google/Amazon/Meta?
Graph connectivity problems using Union-Find and binary search patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include earliest time to connect a network or minimum operations to form components.
What data structure is used in Minimum Time for K Connected Components?
The key data structure is Disjoint Set Union (Union-Find). It efficiently tracks connected components and supports near O(1) union and find operations using path compression and union by rank.
What is the time complexity of Minimum Time for K Connected Components?
The optimal approach runs in O(E log E) time and O(N) space. Sorting edges by timestamp dominates the complexity, while Union-Find operations are almost constant time with path compression and union by rank.