0866MediumArray

Fewest Exchanges to Order the Bays

Tracked in this browser only

Trains the technique from

LeetCode 3942Minimum Operations to Sort a Permutation

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 has n bays numbered 0 through n - 1, and nums is a permutation of those numbers giving the pallet parked in each bay.

One exchange swaps the pallets in any two bays. Return the fewest exchanges that put pallet i in bay i for every i.

Examples

Example 1

Input: nums = [2, 0, 1]
Output: 2

The three bays form a single loop, since bay 0 holds the pallet belonging in bay 2, which holds the one belonging in bay 1, which holds the one belonging in bay 0. Two exchanges settle it.

Example 2

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

Bay 0 is already right, and the other four bays form two loops of two, each settled by a single exchange.

Example 3

Input: nums = [0, 1, 2, 3]
Output: 0

Every pallet is already in its own bay, so no exchange is needed.

Constraints

1 <= nums.length <= 10^5
0 <= nums[i] <= 99999
nums is a permutation of the numbers from 0 to nums.length - 1

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 fewest_exchanges(nums: list[int]) -> int:

Java

public int fewestExchanges(int[] nums)

The intended approach

Time O(n) for n bays: each is walked once.Space O(n) for the visited marks.

Follow where each pallet has to go: from a bay, step to the bay its pallet belongs in, and keep stepping. Because the pallets are a permutation, those steps close into loops that together cover every bay. A loop of length one is already right and costs nothing, and a loop of length `L` needs `L - 1` exchanges, since each exchange can settle at most one more pallet and putting one pallet right shortens the loop by one. Adding that over the loops gives the bay count minus the number of loops.

Pythonentry point: fewest_exchanges

def fewest_exchanges(nums):
    n = len(nums)
    seen = [False] * n
    loops = 0
    for start in range(n):
        if seen[start]:
            continue
        loops += 1
        here = start
        while not seen[here]:
            seen[here] = True
            here = nums[here]
    return n - loops

The obvious version

Search outwards from the given arrangement, one exchange at a time, keeping every arrangement already reached, and report how many rounds it takes for the ordered arrangement to turn up. Explores every exchange rather than reasoning about loops.

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_fewest_exchanges(nums):
    n = len(nums)
    goal = tuple(range(n))
    start = tuple(nums)
    if start == goal:
        return 0
    seen = {start}
    frontier = [start]
    steps = 0
    while frontier:
        steps += 1
        nxt = []
        for state in frontier:
            for a in range(n):
                for b in range(a + 1, n):
                    lst = list(state)
                    lst[a], lst[b] = lst[b], lst[a]
                    cand = tuple(lst)
                    if cand == goal:
                        return steps
                    if cand not in seen:
                        seen.add(cand)
                        nxt.append(cand)
        frontier = nxt
    return 0

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