Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

algorithm
space complexity

What are in-place and out-of-place algorithms?

Educative Answers Team

In-place algorithms are a type of algorithm in computer science that do not require additional space for their operation. Additional variables that consume a small amount of nonconstant memory are acceptable. This extra space should be less than O(log n)O(log\space n), however, below O(n)O(n) is sometimes allowed. The opposite of an in-place algorithm is an out-of-place or not-in-place algorithm.

Updating operations in in-place algorithms usually involve overwriting previous data. Let’s consider two approaches to reversing a list:

  1. out-of-place
  2. in-place

Out-of-place

For an out-of-place algorithm, the simplest solution may be to traverse the original list in reverse and construct another list using that data. Once the list is fully traversed, the new list is constructed.

array = ['a', 'b', 'c', 'd']
new_array = ['a'] * len(array)

print("Before",array)

lenght = len(array) - 1

for i in range(lenght):
    new_array[i] = array[lenght - i]
    
array = new_array
print("After",array) 
1 of 7

In-place

In an in-place algorithm, we will swap the first element of the list with the last element​, and so on, until we’ve completed the operation.

array = ['a', 'b', 'c', 'd']

print("Before",array)

lenght = len(array) - 1

for i in range(lenght // 2 + 1):
    #print("Swapping", array[i], 'and', array[lenght - i])
    
    tmp = array[i]
    array[i] = array[lenght - i]
    array[lenght - i] = tmp

print("After",array) 
1 of 4

RELATED TAGS

algorithm
space complexity
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring