Find the minimum number of swap operations Mary must perform to order all n items by decreasing popularity rating.?

#1

Task

John is a famous shopkeeper who sells n items in her shop. She assigns each item a unique popularity rating in the inclusive range from 1 to n.

The shop only has one shelf, so the items are displayed array-style in a single row spanning from left to right in a random order. He wants to rearrange the items on the shelf by decreasing popularity rating such that the rating for the i item is always greater than the popularity rating of the (i + 1) item. Mary can swap any two items, i and j, in a single operation.

Specification
minimumSwaps(ratings)

Parameters

ratings: Array<Number> - an array of numbers indicating the popularity rating of each item on the shelf.

Return Value

Number - denotes the minimum number of swap operations Mary must perform to order all n items by decreasing popularity rating.

Constraints

n = number of items in ratings array

each rating value ( arri ) will be unique

1 ≤ n ≤ 2 × 105

1 ≤ arri ≤ n

// Here is my solution to the problem above but it does not pass the tests

function minimumSwaps (ratings) {
   var swaps = 0;
   var n = 1;
  for (var i = 1; i < i.length; i++) {
    for (var j = i + 1; j < i.length; j++) {
      if (ratings[i] == ratings[j]) {
        n = n + 1;
      } else {
        swaps = swaps + 1;
      }
    }
  }
  return n;
}
 
console.log(minimumSwaps([3, 1, 2]));
0 Likes

#2

Anyone with a better solution to the above task as my code here is not passing the tests?

Am using javascript

function minimumSwaps (ratings) {
var swaps = 0;
var n = 1;
for (var i = 1; i < i.length; i++) {
for (var j = i + 1; j < i.length; j++) {
if (ratings[i] == ratings[j]) {
n = n + 1;
} else {
swaps = swaps + 1;
}
}
}
return n;
}

console.log(minimumSwaps([3, 1, 2]));

0 Likes

#3

Well just for starters your outer loop loops one too many times.

It’s also important to note that the goal as stated is not to minimize your own code’s complexity; it’s to return the right number.

0 Likes

#4

Hi m_hutley;
It would be great if you can paste a code or improve my code.
Thanks for your positive reply

0 Likes

#5

Well lets start with the theory:

Given input of [4,3,2,1], how many swaps do I need to make to order this array?

0 Likes

#6

2 swaps

0 Likes

#7

and when you put it through your code, you get an answer of…

0 Likes

#8

1 swap

0 Likes

#9

Well you’ve just told me it requires 2. So obviously, your code hasn’t gotten my example correct.

Time to start debugging, yes?

0 Likes

#10

You don’t actually need to sort the list to find out the minimum number of swaps. In fact, you are almost guaranteed to use a much larger number of swaps than the minimum.

Instead of ordering the list, graph theory is used to find the minimum number of swaps.

This sounds a lot like a job interview question, to test whether you know about such things.

0 Likes

#11

Any suggestion in terms of a code here will be of my help m_hutley
Thanks for your positive response

0 Likes

#12

(Ironically, Paul, you actually do need to sort the list… but only insofar as to determine the proper end state to generate a graph from)

0 Likes

#13

Steps:

  1. Figure out the different cycles that are involved
  2. Calculate the size of each cycle
  3. The number of swaps is one less than the size of each cycle.
1 Like

#14

thanks for your positive reply Paul though a code here would sound much easier for me

0 Likes

#15

For example, with [3, 1, 2]

[Edited to account for the reverse order that’s required by the question]

The 3 is in the right place, which is one cycle with a size of 1. The 1 belongs where the 2 is, and the 2 belongs where the 1 is, so that’s a second cycle of size 2.

The size of the two cycles is 1 and 2.

The number of swaps is 1. (first with 0, then second with 1).

With a different array, such as [1, 3, 2], the first cycle is 1 to the last position, the 2 in last position to the middle, and the 3 in the middle to the front. That’s a cycle of size 3, and one less than those is 3 -1 for a total of 2 swaps.

That’s the theory that’s involved.

0 Likes

#16

Hi Paul, any code suggestion will be much easier for me .
Thanks Paul

// Here is my trial code

function minimumSwaps (ratings) {
   var swaps = 0;
   var n = 1;
  for (var i = 1; i < i.length; i++) {
    for (var j = i + 1; j < i.length; j++) {
      if (ratings[i] == ratings[j]) {
        n = n + 1;
      } else {
        swaps = swaps + 1;
      }
    }
  }
  return n;
}
 
console.log(minimumSwaps([3, 1, 2]));
0 Likes

#17

Sorry mate, but I don’t think that its appropriate for me to craft up code for what looks to be your own job interview.

Other similar code though is found at https://www.includehelp.com/java-programs/minimum-swaps-required-to-sort-an-array.aspx

0 Likes

#18

Okay ! Thanks Paul, i will have a look at that link .

Thanks

0 Likes

#19

Zero swaps are needed, based on the requirements. :biggrin:

rearrange the items on the shelf by decreasing popularity rating such that
the rating for the i item is always greater than the popularity rating
of the (i + 1) item
1 Like

#20

Shh Paul, don’t do silly things like actually read the problem :wink:

1 Like