FastPrepMinimum Swaps
Problem · Array

Minimum Swaps

Learn this problem
● MediumAkuna Capital logoAkuna CapitalINTERNOA

Problem statement

You are given an array popularity containing the unique popularity ratings of n items.

The shopkeeper wants the items arranged from left to right in decreasing popularity.

  • In one operation, the shopkeeper can swap any two items.
  • Your task is to determine the minimum number of swaps needed to achieve the correct decreasing order.

Function

minimumSwaps(popularity: int[]) → int

Examples

Example 1

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

Suppose there are n = 4 items, and popularity = [3, 4, 1, 2].

Output: 2

Explanation

  1. First swap: Switch items with ratings 3 and 4 to get [4, 3, 1, 2].
  2. Second swap: Switch items with ratings 1 and 2 to get [4, 3, 2, 1].

Constraints

  • 1 ≤ n ≤ 2 × 10^5
  • 1 ≤ popularity[i] ≤ n
  • Test Case Input Format
    • The first line contains the integer n.
    • The next n lines contain an integer element of popularity[i].

More Akuna Capital problems

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