0721EasyArrayHash TableString

Last Stop On The Courier Run

Tracked in this browser only

Trains the technique from

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.

A courier's shift is written down as a list of legs. Entry legs[i] = [origin, arrival] records one leg driven from the depot named origin straight to the depot named arrival. The legs are jotted down in whatever order they were remembered, not in the order they were driven.

Taken together the legs form a single run that never returns to a depot it has already visited, so exactly one depot ends a leg without ever starting one.

Return the name of that depot, the stop where the run finishes. Depot names are compared character by character, so two names that differ only in letter case or in a space are different depots.

Examples

Example 1

Input: legs = [["Cedar", "Dune"], ["Alder", "Birch"], ["Birch", "Cedar"]]
Output: "Dune"

Alder, Birch and Cedar each start a leg. Dune does not, so the run ends there.

Example 2

Input: legs = [["Wren", "hollow"], ["hollow", "Hollow"]]
Output: "Hollow"

Wren and hollow each start a leg. Hollow with a capital H is a different depot and starts nothing, so the run ends there.

Example 3

Input: legs = [["Port Reed", "Kiln End"], ["Kiln End", "Ash Row"]]
Output: "Ash Row"

Port Reed and Kiln End each start a leg, while Ash Row only ever ends one, so the run finishes at Ash Row.

Constraints

1 <= legs.length <= 100
legs[i].length == 2
1 <= legs[i][j].length <= 10
The two depot names on one leg are different.
Depot names hold uppercase and lowercase English letters and the space character only.
The legs form one run that visits no depot twice, so exactly one depot never starts a leg.

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 final_stop(legs: list[list[str]]) -> str:

Java

public String finalStop(List<List<String>> legs)

The intended approach

Time O(L) for L legs, treating each depot name as a bounded-length key.Space O(L) for the set of starting depots.

Collect the name at the start of every leg into a set, which takes one pass. Then walk the legs again and report the first arrival name that is missing from that set; the run leaves a depot exactly when the depot starts a leg, so the arrival that starts nothing is the finish.

Pythonentry point: final_stop

def final_stop(legs):
    # Every depot that starts a leg goes into a set; the one depot that is the end
    # of a leg without being in that set is where the run finishes.
    # Time O(L) over the legs, treating a name as a fixed-width key.  Space O(L).
    starts = set()
    for leg in legs:
        starts.add(leg[0])
    for leg in legs:
        if leg[1] not in starts:
            return leg[1]
    return ""

The obvious version

Take each arrival name in turn and rescan the whole list of legs looking for a leg that starts at that name. The first arrival for which no such leg turns up is the finish.

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_final_stop(legs):
    for i in range(len(legs)):
        candidate = legs[i][1]
        drives_on = False
        for j in range(len(legs)):
            if legs[j][0] == candidate:
                drives_on = True
                break
        if not drives_on:
            return candidate
    return ""

How this problem was checked

Reference solution executed against 10 test cases — 10 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