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 <= nWhen you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
This search tries every subset of the supplied links, including the subset that keeps nothing. For each subset it merges the endpoints and adds up every kept link's time, even when a link does not create a new merge. It keeps the smallest total among subsets that leave exactly the requested number of groups, and it reports failure when none do.
Here's how the algorithm would work step-by-step:
import itertools
def find_minimum_time_brute_force(number_of_cities, required_components, all_possible_connections):
minimum_total_time = float('inf')
# Generate every possible subset of connections to consider, from size 0 to all connections.
for number_of_connections_to_consider in range(len(all_possible_connections) + 1):
for subset_of_connections in itertools.combinations(all_possible_connections, number_of_connections_to_consider):
parent_array = list(range(number_of_cities + 1))
number_of_components = number_of_cities
def find_root(city):
if parent_array[city] == city:
return city
parent_array[city] = find_root(parent_array[city])
return parent_array[city]
def union_sets(first_city, second_city):
nonlocal number_of_components
first_root = find_root(first_city)
second_root = find_root(second_city)
if first_root != second_root:
parent_array[second_root] = first_root
number_of_components -= 1
current_subset_time = 0
# For the chosen subset of connections, build the graph and calculate its properties.
for time_cost, first_city, second_city in subset_of_connections:
union_sets(first_city, second_city)
current_subset_time += time_cost
# If this subset creates the exact number of required networks, check if it's the new minimum.
if number_of_components == required_components:
minimum_total_time = min(minimum_total_time, current_subset_time)
# After checking all subsets, return the minimum time found, or -1 if no valid configuration exists.
return minimum_total_time if minimum_total_time != float('inf') else -1This search treats the input as points and binary-searches a squared distance bound. For a candidate bound it merges every pair of points whose squared distance falls inside that bound and counts the groups that remain. It records a bound when the group count is at least the target and then tries a smaller bound, otherwise it tries a larger bound, and it finally returns the square root of the recorded squared bound.
Here's how the algorithm would work step-by-step:
def min_time_for_k_components(points, k_components):
number_of_points = len(points)
def get_distance_squared(point_one_index, point_two_index):
x1, y1 = points[point_one_index]
x2, y2 = points[point_two_index]
return (x1 - x2) ** 2 + (y1 - y2) ** 2
def count_components(max_allowed_distance_squared):
parent = list(range(number_of_points))
component_count = number_of_points
def find_representative(node_index):
if parent[node_index] == node_index:
return node_index
parent[node_index] = find_representative(parent[node_index])
return parent[node_index]
def union_sets(first_node_index, second_node_index):
nonlocal component_count
root_one = find_representative(first_node_index)
root_two = find_representative(second_node_index)
if root_one != root_two:
parent[root_two] = root_one
component_count -= 1
for i in range(number_of_points):
for j in range(i + 1, number_of_points):
if get_distance_squared(i, j) <= max_allowed_distance_squared:
union_sets(i, j)
return component_count
low_time_bound = 0
high_time_bound = 0
for i in range(number_of_points):
for j in range(i + 1, number_of_points):
high_time_bound = max(high_time_bound, get_distance_squared(i, j))
min_valid_time_squared = high_time_bound
while low_time_bound <= high_time_bound:
# Pick a time in the middle of the current range to test its feasibility.
guess_time_squared = (low_time_bound + high_time_bound) // 2
if count_components(guess_time_squared) >= k_components:
# This time is a potential answer, so save it and try for an even smaller time.
min_valid_time_squared = guess_time_squared
high_time_bound = guess_time_squared - 1
else:
# This time creates too few components, so we must allow a larger connection time.
low_time_bound = guess_time_squared + 1
return min_valid_time_squared ** 0.5| Case | How to Handle |
|---|---|
| The only selection is the empty set and it already has the requested number of groups | Return zero, because keeping no links costs nothing and leaves every node separate. |
| No selection of links leaves exactly the requested number of groups | Return a negative result after every subset has been rejected. |
| A kept link joins two nodes that are already in the same group | Still add that link's time, and do not reduce the group count a second time. |
| Every pair of points has squared distance zero | Return zero, because the square root of a zero saved bound is zero. |
| A tested squared distance leaves at least the requested number of groups | Save that distance and continue the search toward smaller distances. |
| A tested squared distance leaves too few groups | Discard that distance and continue the search toward larger distances. |