Hey there! Today i am going to publish my first article on In-Place Algorithm . Basically I came to know about this algorithm while solving a question on leetcode. I found this algorithm very useful as it uses constant space for solving a question, However it uses some variables for computation which are of constant space.
What does In-place Algorithm do?
Basically What happens? Whenever we give input to this algorithm, it takes that input, perform some computation on input itself, use some extra varaible (according to requirement). So what we get as a output? It doesn’t return anything, because it has changed our given input according to requirement.
Example:
Let us consider we are given an array [1,2,3,4,5]. we want to reverse this given array and want our output as [5,4,3,2,1]. So basically there are two ways of solving this question:
As shown in the above picture, what we did, we just reverse an array using one more array. In this temp_arr we started inserting from last index, at the last index of temp_arr, we inserted first element of given array. Thus we did this reverse order calculation in O(n) time, but with O(n) extra Space.
Is this the right way to do this problem?
No, not at all. we can use more efficient way to solve this question through which we can reduce space complexity to O(1) Space. we can use In-place Algorithm, but how? just see the below code.
Second Way:
So, The above code uses O(1) Space for reversing the given array, but you might be thinking what is In-place algo is doing here?
As we observe we get that first element is swapped with last element of array, second element of array is swapped with second last element and so on.
So By observing code we just traverse the array until its middle index, and swapped first element with last element and so on. Thus we get the reverse of an array in just O(1) extra Space which is Quite efficient then first algo. This is the magic of In-place algorithm.
Other Application Of In-place Algo:
It is also used in merge sort, In merging operation by using In-place we can reduce memory Space.
You can find more detail about this algorithm on Wikipedia.
Here is the Question which I was talking about in starting of my post.
Thank You.