Minimum Operations to Sort with Rotations Then Swaps
Updated
Problem statement
You are given permutation, an array containing each integer from 1 to n exactly once. You want to sort it into ascending order using two kinds of operations, each costing 1:
- Rotate left: move the first element to the end of the array. For example,
[3, 4, 1, 2]becomes[4, 1, 2, 3]. - Swap: exchange any two elements.
All rotations must happen before the first swap: once you swap, you can no longer rotate. Return the minimum total number of operations needed to sort the array.
Function
minOperations(permutation: int[]) → intExamples
Example 1
permutation = [3,4,1,2]return = 2- Two left rotations turn
[3, 4, 1, 2]into[4, 1, 2, 3]and then[1, 2, 3, 4], which is sorted: 2 operations. - Without rotating, the array needs 2 swaps as well (swap 3 with 1, then 4 with 2), so the answer is 2.
Example 2
permutation = [2,3,4,5,1]return = 4- Rotating would take 4 left rotations to bring
1to the front. - Instead, swap without rotating: the values form one cycle of length 5, which needs 4 swaps, so the answer is 4.
Example 3
permutation = [5,1,2,3,4]return = 1- One left rotation gives
[1, 2, 3, 4, 5], so the answer is 1.
Constraints
1 <= n == permutation.length <= 1000permutationcontains each integer from1tonexactly once.
More Bank of New York Mellon Online Assessment questions
Similar questions at other companies
- Optimal TransferSnowflake · OASnowflake interview questions
- Maximum XOR Elimination ScoreRippling · OARippling interview questions
- Find the Celebrity from Pairwise AcquaintancesAmazon · ONSITE INTERVIEW
- Find the Celebrity from Pairwise AcquaintancesSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Minimum Rounds to Complete All TasksInfosys · OAInfosys interview questions
- Reschedule Meetings for Maximum Free TimeFivetran · OAFivetran interview questions
- Maximum Easy Tasks After RearrangingIBM · OAIBM interview questions
- Minimum Cost K-Capable ModelsMicrosoft · OAMicrosoft interview questions
- Maximum ScoreNVIDIA · OANVIDIA interview questions
- Maximum Distinct Values After Unit AdjustmentsBirla Pivot · OA