Description
Solutions
Minimum Swaps
🤘 INTERN

A shopkeeper in Koxland always each item in a shop a unique popularity rating. To order the items in decreasing popularity from left to right, the shopkeeper can swap any 2 items in one operation. Determine the minimum number of operations needed to reorder the items correctly.

Function Description

Complete the function minimumSwaps in the editor.

minimumSwaps has the following parameters:

  1. int popularity[n]: an array of integers that represents the popularity of each item

Returns

int: the minimum number of swaps to order the items properly

(❀❛ ֊ ❛„)♡ Credit to chizzy_elect 🌺ଓ༉‧.⭒ֶָ֢⋆.·°

Example 1: 

Input:  popularity = [3, 4, 1, 2]
Output: 2 
Explanation:

First switch 3 and 4 to get popularity [4, 3, 1, 2] :)

Then switch 1 and 2 to get [4, 3, 2, 1] :3

The array now is reorderd in 2 operations :>
Constraints:
  • 1 <= n <= 2 * 105
  • 1 <= popularity[i] <= n
Thumbnail 0
Testcase
Result
Case 1

input:

output: