In-place Algorithm in 5 minutes
Let’s look at what is the in-place algorithm with some examples
Table of Content:
- What is the in-place algorithm(with example)?
- Make your hands dirty
- Summary
- Reference
What is the in-place algorithm(with example)?
In computer science, an in-place algorithm is an algorithm that transforms input using no auxiliary data structure. However, a small amount of extra storage space is allowed for auxiliary variables. — From Wikipedia
The Wikipedia explanation is not straightforward. Let’s take reversing a list as an example:
Reverse a list(In-place):
Reverse a list(Non-in-place):
As you can see in this Reverse a list example. The in-place solution only needs O(1) extra memory while the not-in-place need O(n) extra memory.
Make your hands dirty:
You cannot understand one concept until you make your hands dirty. I have prepared some exercises for you to practice with, remember to solve the following questions in-place:
1.https://leetcode.com/problems/sort-colors/
2. https://leetcode.com/problems/sort-an-array/
3.https://leetcode.com/problems/wiggle-sort/
For more exercises, you can look at the following page:
https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms
Summary:
For short, an in-place algorithm means transforming the original input using only constant extra memory. Strictly, an in-place needs only O(1) memory beyond the items being sorted; sometimes O(log(n)) additional memory is considered “in-place”.
Reference:
[1]https://en.wikipedia.org/wiki/In-place_algorithm
[2]https://www.geeksforgeeks.org/in-place-algorithm/
[3] https://www.educative.io/edpresso/what-are-in-place-and-out-of-place-algorithms
