Quick 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.

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

  1. 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.
  2. Shifting an array of length n to the left n times gives back the array you started with.
  3. Once the shifts are chosen, what remains is the fewest swaps that sort one fixed arrangement of 1..n.

Fewest Left Shifts and Swaps to Sort a Permutation

easyBNY MellonSoftware Engineer

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

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

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.

Examples

Example 1
Input
([1],)
Output
0
Notes
Minimum valid n = 1: the array is already sorted, so no operation is needed.
Example 2
Input
([1, 2],)
Output
0
Notes
The n = 2 order that is already sorted needs zero operations.

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.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def min_operations_to_sort(perm: list[int]) -> int:
Sample call
min_operations_to_sort([1])
Language
Case 1
Input
([1],)
Expected
0
Case 2
Input
([1, 2],)
Expected
0

Browse More Questions

Show the approach

Approach

Any valid plan is k left shifts followed by s swaps, costing k + s. Shifting n times gives back the original array, so a plan with k >= n shifts costs exactly n more than the same plan with k mod n shifts; only k = 0..n-1 need to be tried. After k left shifts the array is b[j] = perm[(j + k) % n]. The fewest swaps that sort an arrangement of 1..n is n minus the number of cycles of the mapping j -> b[j] - 1: the sorted array has n cycles, any swap changes the cycle count by exactly one (it splits a cycle when both positions lie in the same cycle and merges two cycles otherwise), and until the array is sorted there is always a swap that splits a cycle. So the answer is the minimum over k of k + n - cycles(k). The loop keeps the best total found so far, starting above any possible answer; because a plan's swap count is never negative, once k reaches the best total no larger shift count can improve it, so the loop stops early. Edge cases: n = 1 and an already sorted array return 0 at k = 0; k = 0 alone always costs at most n - 1, so the answer is below n; several shift counts may tie (for example [2, 1] costs 1 with one swap or one shift), but only the minimum value is returned, so no tie-break is needed.

Time complexity:
O(n^2)
Space complexity:
O(n)