Failed testcases for lilys homework hackerrank

Question

Problem

Whenever George asks Lily to hang out, she's busy doing homework.

George wants to help her finish it faster, but he's in over his head!

Can you help George understand Lily's homework so she can hang out with him?

Consider an array of distinct integers, . George can swap any two elements of the array any number of times. An array is beautiful if the sum of among is minimal possible (after, possibly, performing some swaps).

Given the array , find and print the minimum number of swaps that should be performed in order to make the array beautiful.

Input Format

The first line contains a single integer, , denoting the number of elements in the array. The second line contains space-separated integers describing the respective distinct values of .

Output Format

Print the minimum number of swaps that should be performed in order to make the array beautiful.

Sample Input

4

2 5 3 1

Sample Output

2

Please see a full description here

My Effort

The algorithm I followed was:

1.Create value-position hashmap for the list

2.sort the array

3.Iterate through the list, if the element matches with the sorted list element - continue else increment number of swaps, swap the corresponding elements.

Here is my code

import sys

def count_swaps(sorted_list, num_list, position_map):
    swaps = 0
    for index, num in enumerate(num_list):
        if num != sorted_list[index]:

            swaps += 1
            temp = num_list[index]
            pos = position_map[sorted_list[index]]
            num_list[index] = num_list[pos]
            num_list[pos] = temp


    return swaps


def lilysHomework(arr):
    # Complete this function
    position_map = {}
    arr_copy = []
    for index, num in enumerate(arr):
        position_map[num] = index
        arr_copy.append(num)

    sorted_list_asc = sorted(arr, reverse = True)
    sorted_list_dsc = sorted(arr_copy, reverse = False)

    swaps_a = count_swaps(sorted_list_asc, arr, position_map)
    swaps_d = count_swaps(sorted_list_dsc, arr_copy, position_map)

    return min(swaps_a, swaps_d)

if __name__ == "__main__":
    n = int(input().strip())
    arr = list(map(int, input().strip().split(' ')))
    result = lilysHomework(arr)
    print(result)

But this is failing for 3 test cases and they are huge and I am not able to debug with them.I am trying to debug since 4 hours but no luck

Input of one test case which failed

274
656085744 592976686 3037922 82266352 17574000 344340000 8406892 591292449 569625472 899357375 251327440 301303036 281400020 77370228 15516426 82859300 88364436 39767760 148417500 306863056 10926174 118195200 310408774 309307894 200852782 82193280 424056750 249277128 180368880 477624006 86748948 7434336 48882310 112635040 6614541 503907132 598034610 160500171 70444416 72752680 271416096 30521205 529365648 399367584 129849984 263500556 76737948 464269640 613416088 162724716 163420800 720512988 1217212920 727647624 383190420 8350904 3456024 289141064 123384024 158867856 82005504 36225521 533012608 54370440 17671500 53627000 26597644 855638940 55343960 57828624 108025344 21431808 1182600 265643950 30054300 219553915 74203500 658061160 7502400 931691763 295769136 107345925 80109000 130922055 33544944 65280 452996453 301655430 7828912 425016000 297635898 26861016 739961600 928116 19645470 8691456 5123880 596100015 2735436 25596483 173620720 202797504 161748972 30122300 11082820 574006860 426732182 71136825 105659136 1808140278 450779280 286831620 104683008 938781480 175050736 255681692 67096152 119518575 15449840 25273458 165048960 5642130 85199958 354920488 446786340 131214816 41533296 25766518 90782304 59007600 700369740 122021794 56982366 238027920 434370816 223677580 72463156 355858300 144914616 145950 13822570 19914930 11072100 21450528 124958730 105156800 20843784 781192188 448358850 6139822 95694780 78713888 677177472 9963972 366432768 181113408 725292862 473528052 12864000 518355540 55832070 318508876 89963781 1796290329 844308846 428627693 276255100 123609720 440449488 27589680 426614166 110068200 408846096 620309228 186565236 49051552 561738897 650114105 32646556 7174400 275364045 945364797 3674160 66314292 11073770 14885370 245088324 669628848 33110250 971699976 324099072 259496060 492110802 52206516 508725376 1534995792 148078816 57993375 121071195 381960195 12496176 23728250 159836835 712982980 160098622 909675852 110400300 485423372 30637838 339925836 285371600 13618242 80809650 92375040 265612788 1151909241 234661320 16962144 213417000 269646860 1015650090 117439476 53164566 6946134 89506800 305469360 13406432 292353000 9969642 43982198 23887296 67730660 16384192 218824704 1082660306 1679473908 136336179 39265884 1077096020 464272368 87048192 56752487 156212388 360621525 8472816 17613600 62143172 82696127 79939536 155805468 159499963 262072360 39827904 179532360 2455040 327280740 148409340 73738980 3394872 3082560 225009981 188912256 179487784 340340 315171072 96680664 621206280 536379504 391714074 65055960 105570465 365721408 106712025 286764660

Answer 1

We can solve this question by using 2 maps and 4 arrays.

2 arrays to store the original array and 1 array for storing ascendingly sorted array and 1 array for storing descendingly sorted array.

One thing we need to notice is that for an array to be beautiful it should be sorted (either in ascending or descending order).

---

To determine the minimum number of swaps which are required to convert the given array into sorted one we can use maps.

Our answer would be minimum of the count of swaps taken to convert the array into ascending or descending order.

---

For a more detailed explanation I would suggest you to watch this video by alGOds:

Link: https://youtu.be/W8oGaAEOeRU

---

Answer 2

I don't know how your code was passing even sample tests (tests run before submitting the code for evaluation) - for me it was failing for one of them.

The main problem with your code is that you don't update position_map each time your num != sorted_list[index] - you swap values but not indices.

Initially position_map maps values of num_list to their indices. Then, as you sort num_list based on sorted_list, values in num_list get swapped and so must the indices in position_map (but they don't). Hence, update the indices!

Moreover, if position_map gets modified within count_swaps it cannot be re-used. So, either a copy of it should be sent to count_swaps or it can be created right within count_swaps.

Taking into account the points above the fixed code looks like:

...
def count_swaps(sorted_list, num_list):
    swaps = 0

    position_map = {}
    for index, num in enumerate(num_list):
        position_map[num] = index

    for index, num in enumerate(num_list):
        if num != sorted_list[index]:
            swaps += 1
            pos = position_map[sorted_list[index]]
            # IMPORTANT: update indices within position_map 
            position_map[num_list[index]] = pos
            position_map[num_list[pos]] = index
            # swap values as well
            num_list[index], num_list[pos] = num_list[pos], num_list[index]      

    return swaps


def lilysHomework(arr):
    arr_copy = list(arr)

    sorted_list_asc = sorted(arr, reverse = False)
    sorted_list_dsc = sorted(arr_copy, reverse = True)

    swaps_a = count_swaps(sorted_list_asc, arr)
    swaps_d = count_swaps(sorted_list_dsc, arr_copy)

    return min(swaps_a, swaps_d)
...