Minimum Time For K Connected Components · Interview Problem

Back to problems

Leetcode

Medium

Graphs

Graph Connectivity

Greedy

Sorting

Google

Minimum Time For K Connected Components

Find the minimum time needed until a graph has at least $k$ connected components, given that edges can be activated over time.

Acceptance 0%

Start Practice

Problem Statement

Problem

You are given an undirected graph with $n$ vertices and a set of edges. Each edge becomes available at a certain time. Once the time reaches that value, the edge can be used to connect its endpoints.

Your task is to determine the minimum time $t$ such that, using only the edges with availability time $\le t$ , the graph has at least $k$ connected components.

If the graph already has at least $k$ connected components before any edge is available, the answer is the smallest possible time. If it is impossible to reach at least $k$ connected components under the given rules, return the closest valid sentinel value for the platform context if one is specified; otherwise, reason about the feasibility from the available edges.

This is a connectivity-feasibility problem where the key challenge is to efficiently test how many connected components remain after considering all edges up to a given time.

Input Format

The first line contains integers n and k.
The next line or lines describe the edges of the graph.
Each edge is associated with two endpoints and an availability time.
The exact encoding may vary by platform; the core task is to process edges in nondecreasing time order and determine the earliest time when the number of connected components reaches at least k.

Output Format

Return a single integer representing the minimum feasible time.
If multiple times work, return the smallest one.

Constraints

$1 \le n$
$1 \le k \le n$
Graph is undirected.
Edge availability times can be compared and processed in sorted order.
The intended solution should be efficient for large inputs, typically near $O(m \log m)$ or better per feasibility check with an additional logarithmic search when needed.

Examples

Sample cases returned by the problem API.

Example 1

Input

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

Output

Explanation

At time 1, there are 3 components: {1,2}, {3}, {4}. At time 3, edges (1,2) and (2,3) are available, so the graph has 2 components: {1,2,3} and {4}. This is the earliest time when the number of connected components is at least 2.

Example 2

Input

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

Output

Explanation

Before any edge is available, the graph has 3 connected components, which already satisfies k = 3.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress