The Minimum Time for K Connected Components problem presents a graph with edges that have associated time costs. You must find the minimum time threshold at which the graph, when including only edges with cost ≤ threshold, contains at least K connected components. This Minimum Time for K Connected Components coding problem is a graph connectivity problem solved elegantly with Union-Find and binary search.
PhonePe asks this to test the combination of Union-Find (for dynamic connectivity) with binary search on the answer. Understanding when adding edges by cost changes the number of connected components — and binary searching for the exact threshold — shows mature algorithmic thinking. The union find, graph, sorting, and binary search interview pattern is central here.
Binary search on the time threshold + Union-Find for connectivity. Sort all edges by cost. Binary search on a threshold T: include all edges with cost ≤ T and use Union-Find to count connected components. If components ≥ K, T might be reducible; otherwise increase T. The feasibility check (count components ≤ K) defines the monotonic condition for binary search.
Graph: 5 nodes, edges [(1,2,3), (2,3,5), (3,4,8), (4,5,2)]. Target K = 3.
Problems asking for the "minimum threshold" where a graph property holds are tailor-made for binary search on the answer combined with Union-Find. The key insight is always the monotonic property: if threshold T achieves K components, any T' > T also achieves at least K components (more edges connect things, reducing components). Practice Union-Find with path compression and union by rank — these optimizations are expected in any serious interview answer involving graph connectivity.
