In-Place Algorithm

An in-place algorithm operates directly on its input and changes it, instead of creating and returning a new object. This is sometimes called destructive, since the original input is "destroyed" when it's edited to create the new output.

Careful: "In-place" does not mean "without creating any additional variables!" Rather, it means "without creating a new copy of the input." In general, an in-place function will only create additional variables that are space.

Here are two functions that do the same operation, except one is in-place and the other is out-of-place:

def square_list_in_place(int_list): # enumerate() lets us get the index and element for index, element in enumerate(int_list): int_list[index] *= element # NOTE: We could make this function just return, since # we modify int_list in place. return int_list def square_list_out_of_place(int_list): # we allocate a new list with the length of the input list squared_list = [None] * len(int_list) for index, element in enumerate(int_list): squared_list[index] = element ** 2 return squared_list

Working in-place is a good way to save space. An in-place algorithm will generally have space cost.

But be careful: an in-place algorithm can cause side effects. Your input is "destroyed" or "altered," which can affect code outside of your function. For example:

original_list = [2, 3, 4, 5] squared_list = square_list_in_place(original_list) print "squared: %s" % squared_list # prints: squared: [4, 9, 16, 25] print "original list: %s" % original_list # prints: original list: [4, 9, 16, 25], confusingly! # and if square_list_in_place() didn't return anything, # which it could reasonably do, squared_list would be None!

Generally, out-of-place algorithms are considered safer because they avoid side effects. You should only use an in-place algorithm if you're very space constrained or you're positive you don't need the original input anymore, even for debugging.

Pass Your Interviews with My FREE 7-Day Crash Course

I'll teach you the right way of thinking for breaking down tricky algorithmic coding interview questions you've never seen before.

No prior computer science training necessary—I'll get you up to speed quickly, skipping all the overly academic stuff.

No spam. One-click unsubscribe if you hate it.

Psst. Pass it on.

. . .