FastPrep
Problem · Array

Minimum Swaps

Learn this problem
● MediumAkuna CapitalOA

Problem statement

You are given an integer array popularity, where popularity[i] is the unique popularity rating of the ith item in a shop. The shopkeeper wants to arrange the items in decreasing order of popularity from left to right and may swap any two items in one operation.

Return the minimum number of swaps needed to order the items by decreasing popularity.

Function

minimumSwaps(popularity: int[]) → int

Examples

Example 1

popularity = [3, 4, 1, 2]return = 2
  1. First swap: Swap the items with ratings 3 and 4 to get [4, 3, 1, 2].
  2. Second swap: Swap the items with ratings 1 and 2 to get [4, 3, 2, 1].

The array is properly ordered in 2 operations.

Example 2

popularity = [3, 1, 2]return = 1

Swap the items with ratings 1 and 2 to get [3, 2, 1]. The array is then ordered in 1 operation.

Constraints

  • 1 ≤ n ≤ 2 × 10^5
  • 1 ≤ popularity[i] ≤ n

More Akuna Capital problems

drafts saved locally
public int minimumSwaps(int[] popularity) {
  // write your code here
}
popularity[3, 4, 1, 2]
expected2
checking account