Show problems as
Classic problem #1101MediumArrayUnion-FindSorting

The Earliest Moment When Everyone Become Friends

Real-world version: Earliest Minute The Plots Share Water
Tracked in this browser only
Read The Earliest Moment When Everyone Become Friends on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

An irrigation crew is cutting channels between the plots of a farm, numbered 0 through plots - 1. Each row of channels is [minute, a, b], meaning that at clock reading minute a channel between plot a and plot b was finished. A finished channel carries water both ways and stays open for good, so once two plots are joined by any chain of finished channels they can share water from that clock reading onwards.

The rows arrive in whatever order the crew filed them, not in clock order. No two rows share a clock reading, and no unordered pair of plots is cut more than once.

Return the earliest clock reading at which every plot can share water with every other plot. Return -1 if that never happens. Clock readings are never negative, so -1 cannot be mistaken for one.

Examples

Example 1

Input
channels = [[54, 0, 2], [9, 1, 3], [26, 0, 1], [71, 2, 3]], plots = 4
Output
54

The channels finished by reading 54 are the one at 9 joining plots 1 and 3, the one at 26 joining 0 and 1, and the one at 54 joining 0 and 2, which puts all four plots on one chain.

Example 2

Input
channels = [[17, 0, 1], [40, 2, 3], [8, 1, 2]], plots = 5
Output
-1

The farm has five plots but the log never touches plot 4, so no clock reading links the whole farm.

Example 3

Input
channels = [[600000000, 1, 2], [12, 0, 2], [999999999, 0, 1]], plots = 3
Output
600000000

The channel filed at reading 12 joins plots 0 and 2, and the one at 600000000 brings plot 1 onto the same chain.

Constraints

  • 2 <= plots <= 100
  • 1 <= channels.length <= 10^4
  • channels[i].length == 3
  • 0 <= minute_i <= 10^9
  • 0 <= a_i, b_i <= plots - 1
  • a_i != b_i
  • All the values minute_i are unique.
  • Each unordered pair (a_i, b_i) appears at most once in channels.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def earliest_full_link(channels: list[list[int]], plots: int) -> int:
Java
public int earliestFullLink(int[][] channels, int plots)

More on the same topics