Minimum Left Rotations and Swaps to Sort a Permutation
Company: BNY Mellon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Online Assessment
You are given an array that contains every integer from 1 to n exactly once, and you want to sort it into ascending order with as few operations as possible. Two operations are available:
- **Left shift:** move the first element to the end of the array, so `[a1, a2, ..., an]` becomes `[a2, ..., an, a1]`.
- **Swap:** exchange the elements at any two positions.
Once you have performed a swap, you may not perform any more left shifts. Return the minimum total number of operations.
### Function Signature
```python
def min_operations_to_sort(perm: list[int]) -> int:
```
### Rules
- Each left shift and each swap counts as one operation.
- All left shifts happen before the first swap. Using only shifts, only swaps, or no operation at all is allowed.
- A swap may exchange any two distinct positions; they need not be adjacent.
- Return a single integer: the minimum number of operations after which the array is `[1, 2, ..., n]`.
### Constraints
- `1 <= n <= 1000`, where `n = len(perm)`
- `perm` is a permutation of `1, 2, ..., n`, so every value lies in `[1, n]` and appears once.
### Examples
**Example 1**
```text
Input: perm = [3, 4, 5, 1, 2]
Output: 3
```
Three left shifts give `[4, 5, 1, 2, 3]`, then `[5, 1, 2, 3, 4]`, then `[1, 2, 3, 4, 5]`. Sorting the original array with swaps alone takes four swaps, and no combination of shifts and swaps uses fewer than three operations.
**Example 2**
```text
Input: perm = [5, 1, 2, 4, 3]
Output: 2
```
One left shift gives `[1, 2, 4, 3, 5]`, and swapping the 4 and the 3 sorts it. Neither a single shift nor a single swap sorts the original array.
**Example 3**
```text
Input: perm = [2, 1, 3, 4]
Output: 1
```
Swapping the first two elements sorts the array.
Overview: A coding question about sorting a permutation of 1 to n with two operations: cyclic left shifts, which must all come first, and swaps of any two elements. It asks for the minimum total number of operations and tests reasoning about permutations and about combining two kinds of moves.
Read the full BNY Mellon Software Engineer interview experience this question came from
You are given an array `perm` of length n that contains every integer from 1 to n exactly once. You want to turn it into the ascending array `[1, 2, ..., n]` with as few operations as possible. Two operations are available:
- **Left shift:** move the first element to the end of the array, so `[a1, a2, ..., an]` becomes `[a2, ..., an, a1]`.
- **Swap:** exchange the elements at any two distinct positions; the positions need not be adjacent.
Rules:
- Each left shift and each swap counts as one operation.
- All left shifts happen before the first swap: once you have performed a swap, you may not perform any more left shifts.
- Using only left shifts, only swaps, or no operation at all is allowed.
Implement `min_operations_to_sort(perm)` so that it returns a single integer: the minimum total number of operations after which the array is `[1, 2, ..., n]`. Only this minimum value is returned, even when several different plans reach it. The result is always smaller than n, so it fits in a 32-bit signed integer.
### Example 1
```text
Input: perm = [3, 4, 5, 1, 2]
Output: 3
```
Three left shifts give `[4, 5, 1, 2, 3]`, then `[5, 1, 2, 3, 4]`, then `[1, 2, 3, 4, 5]`. Sorting the original array with swaps alone takes four swaps, and no combination of shifts and swaps uses fewer than three operations.
### Example 2
```text
Input: perm = [5, 1, 2, 4, 3]
Output: 2
```
One left shift gives `[1, 2, 4, 3, 5]`, and swapping the 4 and the 3 sorts it. Neither a single shift nor a single swap sorts the original array.
### Constraints
- `1 <= n <= 1000`, where `n = len(perm)`
- `perm` is a permutation of `1, 2, ..., n`, so every value lies in `[1, n]` and appears once.
Constraints
- 1 <= n <= 1000, where n = len(perm)
- perm is a permutation of 1, 2, ..., n, so every value lies in [1, n] and appears once.
Examples
Input: ([1],)
Expected Output: 0
Explanation: Minimum valid n = 1: the array is already sorted, so no operation is needed.
Input: ([1, 2],)
Expected Output: 0
Explanation: The n = 2 order that is already sorted needs zero operations.
Hints
- Every allowed plan is some number of left shifts followed only by swaps, so consider what the array looks like after each possible number of shifts.
- Shifting an array of length n to the left n times gives back the array you started with.
- Once the shifts are chosen, what remains is the fewest swaps that sort one fixed arrangement of 1..n.