Minimum Operations to Sort a Permutation
Real-world version: Fewest Exchanges to Order the BaysThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def fewest_exchanges(nums: list[int]) -> int:public int fewestExchanges(int[] nums)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 11 test cases: 11 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's