Failing test case

#1

Hi I do not understand why I am failing the test case. My code works against custom test cases that I tested against. Thank you!!!

#2

Hello @klementtan,

Can you explain your logic to me?
Why are you using priority queue?

#3

I use priority queue to maintain the highest value in the remaining elements so that I can determine the elements to swap at every iteration in O(1) time.

So for input
5 2
3 4 1 2 5

i = 0 k = 2
pq.top() = {5,4}
nums = {3, 4, 1, 2, 5}
//swap element 5 and 3
//pop pq
// add {3, 4} to priority queue as element 3 is now at index 4
// k-- i++

i = 1 k=1
pq.top() = {4, 1}
nums = {5, 4, 1, 2, 3}
//pop from pq
//nothing else changes as the top of pq is equal to the ith element
//i++

i = 2 k = 1
pq.top() = {3,4}
nums = {5, 4, 3, 2, 1}
//swap element 3(index 4) with element 1(index 2)
//pq pop
// add {1,4} into the pq as now the element 1 is in index 4
// k-- i++

// terminate as now k = 0

#4

Okay @klementtan,

I have understood the use of it.

But, updating the priority queue is causing issue.
See , following code segment:
pair<int, int> new_curr_pair = make_pair(curr_value, max_index);
pq.push(new_curr_pair);

Here you are inserting the curr_value with updates index but how are you deleting the pair that already exists inside the queue for this curr_value?

Correct it.
Hope, this would help.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.