Skip to main content
Talentd

Minimum Time for K Connected Components - Solution & Explanation

MediumBinary SearchUnion FindGraphSorting9 min readAsked at: Amazon, PhonePe
Practice this problem

Problem Statement

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 = 1 or 2, the graph remains unchanged.
  • At 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:

  • 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 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:

  • Since there are already k = 2 disconnected components {1}, {0, 2}, no edge removal is needed. Thus, the answer is 0.

 

Constraints:

  • 1 <= n <= 105
  • 0 <= edges.length <= 105
  • edges[i] = [ui, vi, timei]
  • 0 <= ui, vi < n
  • ui != vi
  • 1 <= timei <= 109
  • 1 <= 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sort Edges + Union-Find SweepO(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-FindO(E log E + E log T)O(N)Useful when solving minimum/earliest time feasibility problems with monotonic conditions

Video Solution

Leetcode 3608 | Minimum time for k connected components | Leetcode weekly context 457 • CodeWithMeGuys • 449 views views

Watch 4 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Time for K Connected Components with our built-in code editor and test cases.

Practice on FleetCode
Previous

Median of Two Sorted Arrays

Next

Search in Rotated Sorted Array