0449MediumArrayUnion-FindSorting

Earliest Minute The Plots Share Water

Tracked in this browser only

Trains the technique from

LeetCode 1101The Earliest Moment When Everyone Become Friends

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def earliest_full_link(channels: list[list[int]], plots: int) -> int:

Java

public int earliestFullLink(int[][] channels, int plots)

The intended approach

Time O(m log m) for m rows, dominated by the sort; the group merges cost near-constant amortised time each.Space O(m + p) for the sorted rows and the group bookkeeping over p plots.

Put the rows in clock order first, then keep every plot in a disjoint group, merging the two groups a channel touches and holding a running count of how many groups remain. The first channel that drops the count to one is the moment the whole farm is linked, so its clock reading is the answer; if the log runs out first, no such moment exists.

Pythonentry point: earliest_full_link

def earliest_full_link(channels, plots):
    # Open the channels in time order and keep the plots in disjoint groups.
    # O(m log m) for the sort, near-constant work per channel after that.
    owner = list(range(plots))
    size = [1] * plots

    def root(a):
        while owner[a] != a:
            owner[a] = owner[owner[a]]
            a = owner[a]
        return a

    groups = plots
    for minute, u, v in sorted(channels, key=lambda row: row[0]):
        ru, rv = root(u), root(v)
        if ru == rv:
            continue
        if size[ru] < size[rv]:
            ru, rv = rv, ru
        owner[rv] = ru
        size[ru] += size[rv]
        groups -= 1
        if groups == 1:
            return minute
    return -1

The obvious version

For each clock reading in ascending order, build the adjacency of every channel finished by then and walk outwards from plot 0 to see whether all plots are reachable. O(m^2 + m * p).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_earliest_full_link(channels, plots):
    minutes = sorted({row[0] for row in channels})
    for cut in minutes:
        near = [[] for _ in range(plots)]
        for minute, u, v in channels:
            if minute <= cut:
                near[u].append(v)
                near[v].append(u)
        seen = [False] * plots
        seen[0] = True
        stack = [0]
        found = 1
        while stack:
            at = stack.pop()
            for nxt in near[at]:
                if not seen[nxt]:
                    seen[nxt] = True
                    found += 1
                    stack.append(nxt)
        if found == plots:
            return cut
    return -1

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in