Merge Sort - Counting Inversions | Hackerrank Solution | Python | Interview Preparation Kit

hello everyone welcome to my codes and in today's video we are going to solve the question merge sort counting inversions and this is a part of the interview preparation kit which we are going to solve using python if you aren't already subscribed then do subscribe to my channel for coding and other tech related content with that let's get started in an array where the elements that indices i and j where i's less than j form an inversion so they will give us an array in a jumbled order which is not sorted and we have to basically counter the number of swaps to be sorted so technically over here they're calling inversions as swaps as you can see over here in this example you swap four and one and then you swap one and two to each other so basically in two swaps you get a sorted array so that is how we're going to solve this question and they've written mod sort counting conversions so mod sort is basically a divide and conquer algorithm which divides the array in smaller pieces and then sorts them and then the bigger array is sorted it uses recursion and it breaks down the entire array to as small as one unit and then you assign a like return statement for that one unit and then by dividing the entire large array into such small individual components you conquer the entire array that's why it's called divide and conquer so i'll show you how to do this one so first we'll take the length of the array so n equal to length of the array and now we will give the condition for when n is equal to one so when this entire array is broken down into such small pieces that the size of the array is one then what are we supposed to do so for that if n is equal to one we return zero because if it's one then you don't have to swap at all right so it's zero swaps and now we will split array arr in two parts so we'll split them in half like approximate half if they are like even or odd so i'll have n1 equal to n by 2 and i'll put a double division which is a flow division so that it gives an integer and i'll have n2 is equal to n minus n1 so you have basically two sizes for both these smaller arrays and now you assign an array to it so array 1 is equal to array from 0 till n1 and array 2 is equal to array from n1 till the end so now we have our two arrays which are split and now we have to perform count inversions on these two arrays separately and we also have to store the number of swaps done in those particular areas so for that we'll have an answer variable answer which stores the number of swaps so like the number of inversions so for that we'll have count inversion for array 1 plus count inversion for array 2 so basically at this line it will again go into a recursive loop where uh it will find the number of swaps for this array and this array separately and then add it over here and when it goes into that smaller array at this stage it will again break into two parts and basically this thing will keep on happening once it reaches to its smallest form which is of size one it will return zero at first and answer would be zero at that point but after it comes here there still are some conversions or like some swaps that need to be performed and those swaps are if say array1 is equal to 234 after getting sorted and array 2 is equal to 1 to 3 so you still need to get this one which is an array 2 from this position till the first position over here so for this function we still need to add some more swaps to our answer so for that i'll have two variables to loop through array1 and ra2 which is i1 and i2 and we'll assign them 0 for now we loop through array the main array for i in range n as that's the size of it and now we give a condition that if i1 is less than n1 which means that it's still so i1 is basically a part of like i1 is counting through array 1 right now so if i1 is less than n1 and so for i2 we will have if i2 is greater than or equal to n2 because it's basically counting through array two right now or array one of i1 is less than equal to array two of i2 so this condition over here is a large one but what this means is that if i1 is less than n1 and if i2 is greater than n2 so i2 is going through these positions right now or if at index i1 in array1 the value is smaller than the value of whatever is at i2 and array 2. so if this is the condition that is met then array at index i will be assigned array at array1 at index i1 because this particular term is larger than this particular term and i2 is still far away so basically it is still larger than whatever this value is so we keep that value at i position and then we add i2 to the answer and this we are doing because we want to check if a smaller value is in the array arr two then it needs to come all the way like the minimum distance that it's it needs to travel is at least up until this point where it enters array 1 and that is why we add i2 to the answer so just to demonstrate an example again if array 1 is 2 3 four and array two is one four five so this one needs to travel all the way from here till here but for now the minimum distance that it needs to travel is at least from here till here and it should become this at least and now this can be sorted later on when uh i1 reaches index 2 and this condition is met so that is what we are looking for over here and which is why we add i2 to answer and once that is done we increment the value of i1 now coming to the next pretty simple condition else if i2 is less than n2 so if this is the case then we simply uh assign array i equal to array 2 i2 which is whatever the number is so basically in that example we assign one directly to the position ahead and this is what we get and then we increment i to eq like plus equal to one so once we do this we will return answer and keep in mind that whatever is like whatever this answer returns is basically uh like assigned over here in the inner stages of the recursion and only when the entire outermost array is executed that is when this final answer is returned to whatever this print statement is so if we run the code yeah so this is how it is performing it's correct so coming to like we'll just print the answer just to check what exactly is happening inside and we'll run the code so as you can see over here now this is given for two inputs which is this which is already sorted and this one which is not sorted so we'll only see the second one because the first one is zero so it starts from five as like they're of equal size so first you get one so let's see why we get one so the first time it divides this string so it divides n one is equal to 5 divided by 2 and it's flow division so 2.5 becomes 2 and this is what it gets so for 2 1 you need one swap right so that is why you get 1 and for this particular thing three one two it goes into recursion and three is divided by two again which gives you three and one two which like three in itself does not need a salt but three and one two as two separate array elements need one big swap of three which goes over here in the end and that is why you get like two which is over here and the one and the zero that you get is for the first stage of three and one and two where three is a separate uh element and one and two is a separate recursion and for that you get zero and for the next step when three goes all the way behind because three has to jump from here to here and here which is two swaps that's why you get two over here and once that is done so you technically have one two three and one two so the only swap that you need to make is this two from over here and this one over here so you make that swap and counting the three swaps which you previously made you get four over here so if you want to explore how exactly you get this answer you can have like you can put different print statements here and there and check for the values of i1 i2 array1 ra2 and so on and check what exactly is happening there so i'll submit the code now yes so this is how it's done if you like this video then do subscribe to my channel and hit the like button and if there's anything that you want me to solve or like do at all any projects or anything like that then do let me know in the comment section below and with that see you in the next video bye

Channel: Mud Codes

Views: 227

Keywords: array, arrays, python, interview, hackerrank, hackerrank tutorial, python tutorial, data structures, java, coding, programming, course, tutorial, interview preparation, practice, google, facebook, amazon, geeksforgeeks, coding camp, hackathon, youtube, interview tips, interview questions and answers, hackerrank solution, solution, algorithm, merge sort algorithm, merge sort, counting inversions, sorting, cracking the coding interview, ctci

Id: MjUEvidYBxw

Length: 10min 58sec (658 seconds)

Published: Mon Sep 06 2021