0256HardDynamic ProgrammingDepth-First SearchBreadth-First SearchGraph Theory

Retooling the One-Way Corridors

Tracked in this browser only

Trains the technique from

LeetCode 2858Minimum Edge Reversals So Every Node Is Reachable

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 depot holds bays storage bays numbered 0 through bays - 1, joined by bays - 1 one-way corridors. Each entry corridors[i] = [a, b] is a corridor that a cart may drive only from bay a to bay b. Ignore the arrows and the layout is a tree: exactly one route of corridors joins any two bays.

Maintenance can retool a corridor so it runs only the other way, and each retooling is one work order.

For every bay s, report the fewest work orders that let a cart parked at bay s drive to every bay in the depot. Each bay is costed on its own: the corridors always start out as given, so a retooling planned for one bay does not carry over to the next.

Return an array of length bays whose entry s holds that count for bay s.

Examples

Example 1

Input: bays = 4, corridors = [[0, 1], [1, 2], [3, 2]]
Output: [1, 2, 3, 2]

From bay 0 a cart drives to bay 1 and bay 2 as the corridors stand, and one work order on the corridor between bay 3 and bay 2 lets it finish at bay 3. From bay 3 the cart drives straight to bay 2, then needs the corridor into bay 1 and the corridor into bay 0 retooled, which is two work orders.

Example 2

Input: bays = 4, corridors = [[1, 0], [2, 0], [3, 0]]
Output: [3, 2, 2, 2]

All three corridors run into bay 0, so a cart starting there needs all three retooled. A cart starting at bay 1 drives into bay 0 as things stand and needs the other two retooled.

Example 3

Input: bays = 2, corridors = [[1, 0]]
Output: [1, 0]

A cart at bay 1 already drives to bay 0, and a cart at bay 0 needs that single corridor retooled.

Constraints

2 <= bays <= 10^5
corridors.length == bays - 1
corridors[i].length == 2
0 <= corridors[i][0] < bays
0 <= corridors[i][1] < bays
corridors[i][0] != corridors[i][1]
Read without their arrows, the corridors form a tree over the bays

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 corridor_flips(bays: int, corridors: list[list[int]]) -> list[int]:

Java

public int[] corridorFlips(int bays, int[][] corridors)

The intended approach

Time O(n) for n bays: the corridor lists are built once, then walked twice.Space O(n) for the corridor lists, the walk order, the stack and the returned counts.

Store each corridor on both bays, tagged 0 in the direction it already runs and 1 in the direction that needs retooling. One walk from bay 0, driven by an explicit stack, adds up the tags of the corridors as they are crossed away from bay 0, which is the count for bay 0, and records which bay fed which. Then visit the bays in that same walk order: moving the start from a bay to one it feeds only changes the single corridor between them, which now has to be crossed the other way, so the count rises by one when that corridor was already pointing outward and falls by one when it was not.

Pythonentry point: corridor_flips

def corridor_flips(bays, corridors):
    # neighbour, plus 1 when driving that way means flipping the corridor
    links = [[] for _ in range(bays)]
    for corridor in corridors:
        a, b = corridor[0], corridor[1]
        links[a].append((b, 0))
        links[b].append((a, 1))

    # cost for bay 0, walked from an explicit stack so deep chains are safe
    feeder = [-1] * bays
    seen = [False] * bays
    seen[0] = True
    order = []
    stack = [0]
    total = 0
    while stack:
        here = stack.pop()
        order.append(here)
        for there, toll in links[here]:
            if not seen[there]:
                seen[there] = True
                feeder[there] = here
                total += toll
                stack.append(there)

    answer = [0] * bays
    answer[0] = total
    for here in order:
        for there, toll in links[here]:
            if feeder[there] == here:
                answer[there] = answer[here] + 1 - 2 * toll
    return answer

The obvious version

Cost every bay from scratch: start a fresh walk there, add 1 for each corridor crossed against its arrow, and record the total. O(n^2).

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_corridor_flips(bays, corridors):
    links = [[] for _ in range(bays)]
    for corridor in corridors:
        a, b = corridor[0], corridor[1]
        links[a].append((b, 0))
        links[b].append((a, 1))
    answer = []
    for start in range(bays):
        seen = [False] * bays
        seen[start] = True
        queue = [start]
        cost = 0
        while queue:
            here = queue.pop()
            for there, toll in links[here]:
                if not seen[there]:
                    seen[there] = True
                    cost += toll
                    queue.append(there)
        answer.append(cost)
    return answer

How this problem was checked

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