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

# Lily's Homework

# Lily's Homework

purbanski + 25 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)

purbanski + 8 comments Above described solution in python:

def solution(a): m = {} for i in range(len(a)): m[a[i]] = i sorted_a = sorted(a) ret = 0 for i in range(len(a)): if a[i] != sorted_a[i]: ret +=1 ind_to_swap = m[ sorted_a[i] ] m[ a[i] ] = m[ sorted_a[i]] a[i],a[ind_to_swap] = sorted_a[i],a[i] return ret raw_input() a = [int(i) for i in raw_input().split(' ')] asc=solution(list(a)) desc=solution(list(reversed(a))) print min(asc,desc)

jason_dam + 0 comments Thanks. Creating map was the key to get past those time outs.

rahul_jhun2wala + 2 comments Thanks for the explanation and the code but I have a concern. How does the reverse part work? You are reversing the list and then calling the sort function which will again sort it in ascending order. So ultimately you are checking swaps in just one direction. Please share your views.

bfletch + 1 comment The key appears to be that the map is created

*prior*to the sorting, so it indeed is different for the two passes and results in the swaps being done in a different order.Specifically

`i`

in the first`for`

loop is different for the two passes.barnwalnikita1 + 3 comments i didn't get your explanation of reverse work.can you please explain me in brief manner?

bfletch + 0 comments If I understand your question, you are asking why the need to run the algorithm twice, once forward and once in reverse.

The reason for the need to check the reverse case is in the definition of the problem. The requirements are that the array is sorted such the sum of the differences between each two consecutive numbers is minimized. There are two ways to acheive that goal -- ascending and descending sorting the list. The descending sort is the "reverse" in this case.

madhazelnut + 0 comments What he's effectively doing (albeit a little indirectly) is first comparing the input array with an asc-sorted reference, then with a desc-sorted reference and taking the smallest number of swaps of the two. That's how I did it.

srivastavaharsh1 + 0 comments To solve it take care of the descending ones too. A counter case to show we also have to take the descending one. Suppose if the array is-: 3 4 2 5 1 then the output should be 2. 5 4 2 3 1(swap 5 and 3) 5 4 3 2 1(swap 2 and 3) Hence the answer will be 2.

srivastavaharsh1 + 0 comments To solve it take care of the descending ones too. A counter case to show we also have to take the descending one. Suppose if the array is-: 3 4 2 5 1 then the output should be 2. 5 4 2 3 1(swap 5 and 3) 5 4 3 2 1(swap 2 and 3) Hence the answer will be 2.

seanexplode + 1 comment This is my code in python3.

I failed to pass TC #1. What am I doing wrong here?

def homework(n, arr): pos = dict() for i, num in enumerate(arr): pos[num] = i cnt = 0 sorted_arr = sorted(arr) for i in range(len(arr)): if arr[i] != sorted_arr[i]: cnt += 1 new_idx = pos[sorted_arr[i]] pos[arr[i]] = new_idx arr[i], arr[new_idx] = arr[new_idx], arr[i] return cnt n = int(input().strip()) arr = list(map(int, input().strip().split())) asc = homework(n, arr) desc = homework(n, list(reversed(arr))) print(min(asc, desc))

briceparent + 1 comment I had the same issue, even though my solution wasn't the same. It was caused by the fact that I was calling my solving function with

`arr`

directly instead of a copy of it. As in the function itself,`arr`

is modified, the second call wasn't made using initial data but using modified data.asc = homework(n, list(arr)) # -> works

also, I like the syntax:

asc = solve(s, ar[::]) desc = solve(s, ar[::-1])

seanexplode + 0 comments Thanks a lot!

19998sachinyadav + 1 comment Thanks. Creating map was the key to get past those time outs.

zhuanzhl + 0 comments nice pun

matt_murdock + 0 comments a[i],a[ind_to_swap] = sorted_a[i],a[i]

can you explain this piece of code

skvit001 + 0 comments [deleted]abhijeetgholap01 + 1 comment I see that you're comparing elements that are out of place and incrementing number of swaps (ret) value. But that is not neccessarily, number of minimum of swaps required.

for example, array1: 2 5 3 1 array2: 1 2 3 5

have 3 elements out of place. but minimum number of swaps required are 2. I would appreciate you can help me understand the algorithm.

Thanks

LordGameleo + 0 comments Check it for reverse array1: 1 3 5 2 - it require two swaps. We are only taking min of ascending and descending.

c_m_s_gan + 0 comments Correction:

def lilysHomework(a): m = {} a_original = a.copy() for i in range(len(a)): m[a[i]] = i sorted_a = sorted(a) ret = 0 for i in range(len(a)): if a[i] != sorted_a[i]: ret +=1 ind_to_swap = m[ sorted_a[i] ] m[ a[i] ] = m[ sorted_a[i]] a[i],a[ind_to_swap] = sorted_a[i],a[i] ret2 = 0 m = {} a = a_original.copy() for i in range(len(a)): m[a[i]] = i for i in range(len(a)): if a[i] != sorted_a[len(a)-1-i]: ret2 +=1 ind_to_swap = m[ sorted_a[len(a)-1-i] ] m[ a[i] ] = m[ sorted_a[len(a)-1-i]] a[i],a[ind_to_swap] = sorted_a[len(a)-1-i],a[i] return min(ret,ret2)

Tried and tested - passes all cases.

Can someone please tell me why my initial attempt timeouts? Here, a histogram array was used to construct a cumulative frequency array of the elements, which was then used as the keys for the correct positions of the numbers in the original array (similar to the Minimum Swaps 2 problem at https://www.hackerrank.com/challenges/minimum-swaps-2/ ):

def lilysHomework(arr): arr_original = arr.copy() b = [None]*(max(arr)+1) l = len(arr) k = (max(arr)) hist = (k+1)*[0] #indices runs from 0 to max(array) inclusive for i in arr: hist[i] = 1 #Initial frequency array, jth value of count is the frequency of number j cumfreq = (k+1)*[0] cumfreq[0] = hist[0] invcumfreq = {} for j in range(1,k+1): cumfreq[j] += cumfreq[j-1] + hist[j] if not(cumfreq[j] in invcumfreq): invcumfreq[cumfreq[j]] = j ## Create an array to get the inverse cumulative frequencies array: counter1 = 0 for j,v in enumerate(arr_original): b[v] = j for j in range(l): if cumfreq[arr[j]] - 1 != j: old = arr[j] # old arr[j] arr[j], arr[b[invcumfreq[j+1]]] = arr[b[invcumfreq[j+1]]], arr[j] #arr[j], arr[b[cumfreq.index(j+1)]] = arr[b[cumfreq.index(j+1)]], arr[j] b[old], b[arr[j]] = b[arr[j]], b[old] counter1 += 1 else: continue arr = arr_original.copy() ##Reset the b-array of indices!! for j,v in enumerate(arr_original): b[v] = j counter2 = 0 for j in range(0,l): if cumfreq[arr[j]] != l - j: old = arr[j] # old arr[j] arr[j], arr[b[invcumfreq[l-j]]] = arr[b[invcumfreq[l-j]]], arr[j] #arr[j], arr[b[revfreq.index(l-j)]] = arr[b[revfreq.index(l-j)]], arr[j] b[old], b[arr[j]] = b[arr[j]], b[old] counter2 += 1 else: continue return counter1 #(min(counter1,counter2))

anshumaan_dash + 2 comments How does this algorithm deal with repeated elements?

purbanski + 1 comment From problem description : "Consider an array of

**distinct**integers "...anshumaan_dash + 0 comments My bad. :p

noobCoder1997 + 0 comments there are no repeated elements ...all the elements are distinct.check the problem statement

SidSam + 0 comments [deleted]gara314 + 0 comments Thank you for reverse. Min sum could be for ascent order as well as for decent order.

hemanth_kgp + 1 comment How to map in c without dictionaries??Direct addressing would take lot of storage which is dependant on values of the input sequence..?

AKSHAY97 + 0 comments You can't map in c. You need to use c++ language

ayushr2 + 1 comment could you pls explain why we reverse the list and run the same algorithm? i wrote a solution which is exactly same but I had not compared with the reversed list. So i was failing in some TCs. But i fail to see how sometimes reverse gives you the correct answer.

mark_anthony_ma1 + 1 comment Yes could someone please explain why just checking the reverse is exhaustive enough?

dshan1 + 0 comments Sorting in either ascending or descending order will give us a beautiful array, but based on the original array, swapping to two different orders will give us two different results, and we want the smaller one

kbhaskar580 + 1 comment ur algo really helped me a lot...thank u..keep helping..

purbanski + 0 comments This is really nice comment. Thank you :)

abhishekvanjani + 1 comment will this work if array has same entries, as key for a map MUST BE UNIQUE??

purbanski + 0 comments I wrote it 8 months ago :) anyway - definetly algo would need to be updated if entries are not distinc. However - from problem description : "Consider an array of distinct integers "...

vaibhavpseud + 0 comments I used this logic, everything works but tests #1,#2,#3,#6 fail. Is there something special for these tests which needs to be handled & which is not mentioned in the threads?

joaonoch + 0 comments CPP14 Implementation:

#include <iterator> #include <map> using namespace std; #define FOR(i,n) for(long (i)=0;(i)<(n);((i)++)) int main() { map<long,long> iMap, iMap2; long iNum, index1, index2; cin >> iNum; index1=index2=0; long iArr[3][iNum]; FOR(i,iNum){ cin >> iArr[0][i]; iMap[iArr[0][i]]=i; } iMap2=iMap; copy_n(iArr[0],iNum,iArr[1]); copy_n(iArr[0],iNum,iArr[2]); sort(iArr[1],iArr[1]+iNum); FOR(i,iNum){ if(iArr[1][i]!=iArr[0][i]){ index1++; iArr[0][iMap[iArr[1][i]]]=iArr[0][i]; iMap[iArr[0][i]]=iMap[iArr[1][i]]; } if(iArr[1][iNum-1-i]!=iArr[2][i]){ index2++; iArr[2][iMap2[iArr[1][iNum-1-i]]]=iArr[2][i]; iMap2[iArr[2][i]]=iMap2[iArr[1][iNum-1-i]]; } } cout << min(index1,index2); return 0; }

ashley247 + 1 comment import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; import java.util.Collections.*; public class Solution { public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner sc = new Scanner(System.in); int n,count=0,count1=0; n= sc.nextInt(); int []b= new int[n]; Integer []a= new Integer[n]; int []c= new int[n]; HashMap map = new HashMap(); HashMap map1= new HashMap(); for(int i=0;i<n;i++){ int num=sc.nextInt(); map.put(num,i); map1.put(num,i); a[i]=num; b[i]=num; c[i]=num; } Arrays.sort(a); for(int i=0;i<n;i++){ if(a[i]!=b[i]){ count++; int temp= b[(int) map.get(a[i])]; int x=b[(int) map.get(a[i])]; b[(int) map.get(a[i])]=b[i]; b[i]=temp; map.put(b[(int) map.get(a[i])],(int) map.get(b[i])); } } Arrays.sort(a,Collections.reverseOrder()); for(int i=0;i<n;i++){ if(a[i]!=c[i]){ count1++; int temp= c[(int) map1.get(a[i])]; int x=c[(int) map1.get(a[i])]; c[(int) map1.get(a[i])]=c[i]; c[i]=temp; map.put(c[(int) map1.get(a[i])],(int) map1.get(b[i])); } } if(count1>count) System.out.println(count); else System.out.println(count1); } }

Doesnt run for test case 2 3 and 9 Why???

lamnguyen2187 + 1 comment `map1`

has to contain indices of the reserve of the input numberskarthickaccet901 + 0 comments I too have the same issue.

what do you mean by indices of the reserve of the input numbers. I don't understand. could you please explain?

ishansrivastava1 + 0 comments "Then you need to execute it on input list and reversed input list - the smaller return value - is the answer." CAN YOU PLEASE EXPLAIN WHAT IS THIS LINE? I DIDNT GET IT

devinludwig + 0 comments This approach in Ruby:

n = gets.to_i a = gets.strip.split.map &:to_i def find_swaps(a) map = a.each_with_index.map{|x,i| [x,i]}.to_h swaps = 0; sort = a.sort for i in 0...a.size do if sort[i] != a[i] swaps += 1 map[a[i]] = map[sort[i]] a[map[sort[i]]], a[i] = a[i], sort[i] end end swaps end puts [find_swaps(Marshal.load(Marshal.dump(a))),find_swaps(a.reverse)].min

aishm_149 + 0 comments I tried to implement your algorithm but I am getting half test cases as wrong answer. Can you help?

# include

using namespace std;

int main() { int n; vectora; cin>>n; int u,temp1; maph; for(u=0;u>temp1; a.push_back(temp1); h[temp1]=u; } vectorb(a.begin(),a.end()); vectorc(a.begin(),a.end()); sort(b.begin(),b.end()); int count_a=0; int count_b=0; int i,j,sec; for(i=0;i()); for(i=0;i

skvit001 + 0 comments I came up with a similar but not exactly the same approach in which i just counted mismatches and thought to apply some function on mismatches that would directly give swaps:

if mismatches%2: return mismatches//2 + 1 else: return mismatches//2

But it somehow fails test case 1, 2, 3, 6. In the end I decided to go with actually swapping and counting it

Isn't there any such function that could direcly be applied on mismatch count to yield number of swaps?

homeworkprospect + 0 comments ackage algorithms.sorting;

import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.Scanner;

public class LilysHomework {

`public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] arr = new int[n]; int[] sorted = new int[n]; int[] reversed = new int[n]; Map<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < n; i++){ arr[i] = in.nextInt(); sorted[i] = arr[i]; reversed[i] = -arr[i]; map.put(arr[i], i); } in.close(); int[] diffs = new int[n]; diffs[0] = 0; for(int i = 1; i < n; i++){ diffs[i] = arr[i] - arr[0]; } Arrays.sort(diffs); int pos = 0; int neg = 0; for(int diff : diffs){ if(diff > 0){ pos++; } if(diff < 0){ neg++; } } boolean sortAscending = pos > neg; if(sortAscending){ Arrays.sort(sorted); } else { Arrays.sort(reversed); for(int i = 0; i < n; i++){ reversed[i] *= -1; } sorted = reversed; } int swaps = 0; for(int i = 0; i < n; i++){ if(sorted[i] != arr[i]){ swaps++; int target = map.get(sorted[i]); int temp = arr[target]; arr[target] = arr[i]; arr[i] = temp; map.put(arr[target], target); } } System.out.println(swaps); /* 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) */ }`

sagban + 0 comments Thanks! for the reverse, from yesterday I was just seeing my code. Although, after using reverse I am still getting tc 1, 2, 3 , 4 failed :(

adamxtokyo + 0 comments Great explanation, but it was a bit hard to follow without code to lean back on. This is my solution for JavaScript if anyone needs it (it was a b*tch to optimize...):

'use strict' let input = '' process.stdin.resume() process.stdin.setEncoding('utf-8') process.stdin.on('data', data => input += data) process.stdin.on('end', () => main()) function main() { input = input.split('\n') let n = Number(input[0]) let arr = input[1].split(' ').map(x => Number(x)) let result = lilysHomework(n, arr) return console.log(result) } function lilysHomework (n, arr) { const swaps = (arr, sarr) => { let [s, idx] = [0, []] arr.forEach((v,i) => idx[v] = i) for (let i = 0, j; i < n; i++) { while (arr[i] === sarr[i] && i < n) i++ j = idx[sarr[i]] idx[arr[i]] = j arr[i] = [ arr[j], arr[j] = arr[i] ][0] s++ } return s-1 } let asc = [...arr].sort((a,b) => a-b) let desc = [...asc].reverse() let s1 = swaps([...arr], asc) let s2 = swaps(arr, desc) return Math.min(s1, s2) }

angelopolotto + 0 comments I found another way to achieve the objective, this problem is very close to the minimum swaps problem, wich the objective is count the minimum swaps to sort a array (https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/):

`from collections import defaultdict def swaps(arr_e): vis = defaultdict(bool) ans = 0 j = 0 for i in range(len(arr_e)): if vis[i] or arr_e[i][0] == i: continue j = i cycles = 0 while not vis[j]: vis[j] = True j = arr_e[j][0] cycles += 1 if cycles > 0: ans += cycles - 1 return ans # Complete the lilysHomework function below. def lilysHomework(arr): arr_e = list(enumerate(arr)) arr_s = sorted(arr_e, key=lambda x: x[1]) ans1 = swaps(arr_s) arr_s = sorted(arr_e, key=lambda x: x[1], reverse = True) ans2 = swaps(arr_s) return min(ans1, ans2)`

sarathy_v_krish1 + 0 comments C++ solution :

int lilysHomework(vector<int>& arr) { vector<int> temp = arr, sorted = arr; sort(sorted.begin(), sorted.end()); unordered_map<int, int> m, mtemp; int count, count1=0, count2=0; for (int i=0;i<arr.size();i++) m[arr[i]]=i; mtemp=m; for (int i=0;i<sorted.size();i++) if (sorted[i]!=arr[i]) { count1++; swap(arr[i], arr[m[sorted[i]]]); m[arr[m[sorted[i]]]]=m[sorted[i]]; } reverse(sorted.begin(), sorted.end()); arr=temp; m=mtemp; for (int i=0;i<sorted.size();i++) if (sorted[i]!=arr[i]) { count2++; swap(arr[i], arr[m[sorted[i]]]); m[arr[m[sorted[i]]]]=m[sorted[i]]; } return count=min(count1, count2); }

snehitha2110 + 0 comments for 0<=i if they are not equal increment s. s-1 would be the answer.

i.e, no.of elements that are not in right place - 1kaushikamardas + 0 comments Thanks mate. Nice algo. I didn't understand it at first, but then I solved it using pen and paper using this algo and then got the gist of it.

The idea is to sort the given array and then compare each element of the given array with the sorted array . If the elements in the given array don't match move the offending element to the position of the correct element and bring the correct element in the the position of the offending element. And using a hashmap to store the indexes for O(1) lookup. Ofcourse this works because there are no duplicate elements in the given array.

Cheers!

suparnasnair + 0 comments Hi, I tried the above solution. However, I have some doubt.

`m[a[i]] = m[s[i]]`

`a[i], a[m[s[i]]] = s[i], a[i]`

In the above code snippet, I had earlier tried with these two sentences swapped, which didn't give me a correct answer. I am not able to understand why swapping these statements made a difference. Can you please give me insights on this?PranavBansal + 0 comments [deleted]PranavBansal + 0 comments I have done the same thing but still i am not getting the answer

int lilysHomework(vector<int> arr) { int swaps=0; vector<int> sorted; sorted=arr; sort(sorted.begin(),sorted.end()); map<int,int> count; for(int i=0;i<arr.size();i++) count[arr[i]]=i; for(int i=0;i<arr.size();i++){ if(arr[i]!=sorted[i]){ swaps++; int temp1=arr[i],temp2=sorted[i]; swap(arr[i],arr[count[temp2]]); count[temp1]=count[temp2]; } } return swaps; }

For the input

3 4 2 5 1

I am doing these swaps

1 4 2 5 3 1 2 4 5 3 1 2 3 5 4 1 2 3 4 5

Total swaps here are 4 but the expected outcome is 2

What am I doing wrong here?

- create map with:

JedJulliard + 1 comment George should understand that Lily is not interested in hanging out

gjmhfs + 0 comments :) Same thing I was thinking!

annjohny10 + 4 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!

belushkin + 0 comments Great, thank you for the help, I will check it later!

sayansingha + 0 comments hey, if the numbers in the unsorted array are not serial then what do we do? for example: original array: 72 3 0 4 1 6 5 2 thanks

aryangarg1999 + 0 comments You explained it very nicely .... Thank u so much for helping me...

SyedSafdarAli + 1 comment Very nice explanation but I have one doubt what if the array have duplicate elements like: 7 3 0 4 1 0 5 0 because now "0" is present at index [2], [5], [7] , so in the first swap at which index we are going to swap "7" with.

xakerr + 0 comments The elements are distinct.

- You have to sort the array in both

psavine42 + 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.

victorgf + 2 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?

sergiu_nacu + 0 comments [deleted]goodengineer + 1 comment Hey, counter example here:

`5 3 4 2 1 5`

the expected output is 3, but with your logic:

`3 4 2 1 5 1 2 3 4 5 --------- 1 1 1 1 0 && 3 4 2 1 5 5 4 3 2 1 --------- 1 0 1 1 1`

the output is ceil(4/2) = 2

The flaw in your logic is that you assume that two different positions between the input array and the sorted input array are fixed with only 1 swap, when in reality it's a bit more complex than that.

v_vendetta + 0 comments reply guys

Sort 117 Discussions, By:

Please Login in order to post a comment