Watch 5 video solutions for Minimum Time for K Connected Components, a medium level problem involving Binary Search, Union Find, Graph. This walkthrough by CodeWithMeGuys has 396 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
{0, 1}.time = 1 or 2, the graph remains unchanged.time = 3, edge [0, 1] is removed, resulting in k = 2 connected 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:
{0, 1, 2}.time = 2, edge [0, 1] is removed, resulting in two connected components {0}, {1, 2}.time = 4, edge [1, 2] is removed, resulting in k = 3 connected components {0}, {1}, {2}. Thus, the answer is 4.Example 3:
Input: n = 3, edges = [[0,2,5]], k = 2
Output: 0
Explanation:
k = 2 disconnected 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 <= nProblem 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.
| 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 |