- Prepare
- Algorithms
- Sorting
- Lily's Homework
- Discussions

# Lily's Homework

# Lily's Homework

+ 9 comments George should understand that Lily is not interested in hanging out

+ 35 comments I've done it :) Passing all test :) My approach is:

Prep stage:

- create map with:
- keys : values from input list,
- values : indexes of values from input list,

- make a copy of sorted input list

Algo stage:

Iterate through input list, and compare current value (lets call it cv) against value from sorted list (lets call it scv). If it is diffrent:

- increment number of swaps
- get index of the scv from map - map[scv],
- in input list swap cv with scv,
- update map[cv]=map[scv] (map[scv] does not need to be updated as we are not going to use it any more)

Then you need to execute it on input list and reversed input list - the smaller return value - is the answer.

Time complexity is equal to sort time complexity (usually O(n logn) ). Space O(n)

- create map with:

+ 14 comments **Finally solved it**! Spent some time trying to figure out the hidden details. Would appreciate if there had been another test case. Things i learnt - Java specifics (*might be useful if you're stuck*):- You have to sort the array in both
**ascending**and**descending**order as both will yield a minimum sum. - Remember to use a
**LinkedHashMap**(if you are using one) and not a HashMap to store the element key and index value (to preserve insertion order). - A copy of an ArrayList is a
**shallow copy**. You need to`addAll(originalArray)`

to create another array with the same values as the originalArray.

The algorithm is pretty simple: (just a brief run-through , note the details, figure out the implementation)

**compare**every element of original array with a copy of the sorted array (refer 3)- when there's a mismatch,
**swap**elements into their respective positions **count**the total number of swaps- repeat the above with the array reversed (refer 1)
- use a hashmap as a cache/lookup to speed things up O(1) (refer 2).

Example:

**7 3 0 4 1 6 5 2 - original array****0 1 2 3 4 5 6 7 - sorted array****0**3**7**4 1 6 5 2 - after first swap0

**1**7 4**3**6 5 2 - after second swap0 1

**2**4 3 6 5**7**- after third swap0 1 2

**3****4**6 5 7 - after fourth swap0 1 2 3 4

**5****6**7 - after fifth swapDid you notice the pattern? All the best!

- You have to sort the array in both

+ 0 comments I take issue with the problem. I propose that the solution is to not help Greg in the first place, and ask Lily out myself.

+ 3 comments In this problem, my intuition was telling me to just count the different positions between the input array and the sorted input array and then divide this count between 2 rounding up. For example: input array: 1 5 3 4 sorted array: 1 3 4 5 count: 0 1 1 1 = 3 number of swaps = ceil(3/2) = 2

In all the cases that I have tried I get the correct answer. I take into account normal and reverse order. However, test cases #1,#2,#3,#6 give me a wrong answer. Could someone tell me the problem in my reasoning or give me a counter example?

Sort 237 Discussions, By:

Please Login in order to post a comment