0245HardArrayStringDepth-First SearchGraph TheorySortingHeap (Priority Queue)Eulerian CircuitEulerian PathSemi-Eulerian Graph

Haul Permit Run

Tracked in this browser only

Write code

Trains the technique from

LeetCode 332Reconstruct Itinerary

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 regional courier holds a bundle of one-way haul permits. Each permit is written [origin, destination], a pair of three-letter uppercase depot codes, and it entitles the van to drive that leg exactly once. No permit names the same depot twice, and two permits may cover the very same leg, in which case that leg is driven twice.

The van sets out from the depot coded "HUB" and has to spend the whole bundle: every permit is driven exactly once. The bundle is always one that allows this.

Report the run as the list of depot codes the van stands at, in order: "HUB" first, then the destination of each leg as it is driven. The list therefore holds one more code than the bundle holds permits.

Several runs may spend the whole bundle. Return the smallest of them under front-to-back comparison: read two candidate runs position by position from the start, and the one holding the smaller depot code at the first position where they differ is the one to return.

Examples

Example 1

Input: permits = [["HUB", "ARL"], ["HUB", "BEC"], ["BEC", "HUB"]]
Output: ["HUB", "BEC", "HUB", "ARL"]

The run drives HUB to BEC, BEC back to HUB, then HUB to ARL, which spends all three permits and stands the van at four depots in turn.

Example 2

Input: permits = [["HUB", "ARL"], ["ARL", "BEC"], ["BEC", "CDR"]]
Output: ["HUB", "ARL", "BEC", "CDR"]

Each depot issues a single permit onward, so the bundle chains into one run and there is nothing to compare.

Example 3

Input: permits = [["HUB", "ARL"], ["HUB", "BEC"], ["ARL", "HUB"], ["BEC", "HUB"]]
Output: ["HUB", "ARL", "HUB", "BEC", "HUB"]

Two runs spend the bundle: this one and the run that visits BEC before ARL. They first differ at position 1, where ARL is the smaller code.

Constraints

1 <= permits.length <= 300
permits[i].length == 2
Each depot code is exactly 3 uppercase English letters
permits[i][0] != permits[i][1]
At least one run starting at "HUB" drives every permit exactly once

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 plan_hauls(permits: list[list[str]]) -> list[str]:

Java

public List<String> planHauls(List<List<String>> permits)

The intended approach

Time O(m log m) for m permits, dominated by sorting the groups.Space O(m) for the groups, the stack and the returned run.

Group the permits by origin and sort each group so the smallest code is always the next one taken from it. Push "HUB" on a stack and keep consuming permits out of whatever depot is on top; when a depot has no permit left, pop it and record it. The recorded depots come out in reverse, so reverse them at the end.

Pythonentry point: plan_hauls

def plan_hauls(permits):
    onward = {}
    for permit in permits:
        onward.setdefault(permit[0], []).append(permit[1])
    for origin in onward:
        onward[origin].sort(reverse=True)
    run = []
    stack = ["HUB"]
    while stack:
        here = stack[-1]
        options = onward.get(here)
        if options:
            stack.append(options.pop())
        else:
            run.append(stack.pop())
    run.reverse()
    return run

The obvious version

Exhaustive search: from the current depot try each distinct onward permit in code order, recurse, and undo the choice when the branch cannot spend the bundle. The first complete run found is the answer. Exponential in the worst case.

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_plan_hauls(permits):
    onward = {}
    for permit in permits:
        onward.setdefault(permit[0], []).append(permit[1])
    for origin in onward:
        onward[origin].sort()
    total = len(permits)
    run = ["HUB"]

    def walk(here, driven):
        if driven == total:
            return True
        options = onward.get(here)
        if not options:
            return False
        tried = set()
        for i in range(len(options)):
            target = options[i]
            if target in tried:
                continue
            tried.add(target)
            options.pop(i)
            run.append(target)
            if walk(target, driven + 1):
                return True
            run.pop()
            options.insert(i, target)
        return False

    walk("HUB", 0)
    return list(run)

How this problem was checked

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